Pasar al contenido principal

COMBINATORIA: NUEVAS TENDENCIAS Y APLICACIONES

PID2020-113082GB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2020
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 68
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Vilar Algueró, Ricard
© 20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works, We prove that there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n¿q2 over Fq2 if and only if there is a polynomial g¿Fq2 of degree at most (q-k)q-1 such that g+gq has q2-n distinct zeros. This allows us to determine the smallest n for which there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n over Fq2 , verifying a conjecture of Grassl and Rötteler. We also provide examples of Hermitian self-orthogonal k -dimensional generalised Reed-Solomon codes of length q2+1 over Fq2 , for k=q-1 and q an odd power of two., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On additive MDS codes with linear projections

  • Adriaensen, Sam
  • Ball, Simeon Michael|||0000-0003-4845-2084
We support some evidence that a long additive MDS code over a finite field must be equivalent to a linear code. More precisely, let C be an -linear MDS code over . If , , , and C has three coordinates from which its projections are equivalent to -linear codes, we prove that C itself is equivalent to an -linear code. If , , and there are two disjoint subsets of coordinates whose combined size is at most from which the projections of C are equivalent to -linear codes, we prove that C is equivalent to a code which is linear over a larger field than ., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On additive MDS codes over small fields

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Gamboa Jimenez, Gonzalo
  • Lavrauw, Michel
Let $ C $ be a $ (n,q^{2k},n-k+1)_{q^2} $ additive MDS code which is linear over $ {\mathbb F}_q $. We prove that if $ n \geq q+k $ and $ k+1 $ of the projections of $ C $ are linear over $ {\mathbb F}_{q^2} $ then $ C $ is linear over $ {\mathbb F}_{q^2} $. We use this geometrical theorem, other geometric arguments and some computations to classify all additive MDS codes over $ {\mathbb F}_q $ for $ q \in \{4,8,9\} $. We also classify the longest additive MDS codes over $ {\mathbb F}_{16} $ which are linear over $ {\mathbb F}_4 $. In these cases, the classifications not only verify the MDS conjecture for additive codes, but also confirm there are no additive non-linear MDS codes which perform as well as their linear counterparts. These results imply that the quantum MDS conjecture holds for $ q \in \{ 2,3\} $., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Griesmer type bounds for additive codes over finite fields, integral and fractional MDS codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Lavrauw, Michel
  • Popatia, Tabriz Arun Avery|||0009-0003-0220-4277
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10623-024-01519-2, In this article we prove Griesmer type bounds for additive codes over finite fields. These new bounds give upper bounds on the length of maximum distance separable (MDS) codes, codes which attain the Singleton bound. We will also consider codes to be MDS if they attain the fractional Singleton bound, due to Huffman. We prove that this bound in the fractional case can be obtained by codes whose length surpasses the length of the longest known codes in the integral case. For small parameters, we provide exhaustive computational results for additive MDS codes, by classifying the corresponding (fractional) subspace-arcs. This includes a complete classification of fractional additive MDS codes of size 243 over the field of order 9., The first and third author are supported by the Spanish Ministry of Science, Innovation and Universities grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033 and grant PID2023-147202NB-I00
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Random cubic planar maps

  • Drmota, Michael
  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Requile, Clement|||0000-0002-7689-7972
  • Rué Perna, Juan José|||0000-0002-6420-3179
We analyse uniform random cubic rooted planar maps and obtain limiting distributions for several parameters of interest. From the enumerative point of view, we present a unified approach for the enumeration of several classes of cubic planar maps, which allow us to recover known results in a more general and transparent way. This approach allows us to obtain new enumerative results. Concerning random maps, we first obtain the distribution of the degree of the root face, which has an exponential tail as for other classes of random maps. Our main result is a limiting map-Airy distribution law for the size of the largest block L, whose expectation is asymptotically n/v3 in a random cubic map with n+ 2 faces. We prove analogous results for the size of the largest cubic block, obtained from L by erasing all vertices of degree two, and for the size of the largest 3-connected component, whose expected values are respectively n/2 and n/4. To obtain these results we need to analyse a new type of composition scheme which has not been treated by Banderier et al. [Random Structures Algorithms 2001]., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Polynomials for marked graphs and the chromatic symmetric function

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Approximation and decomposition in lattices of clutters

  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Mier Vinué, Anna de|||0000-0002-2817-7807
A clutter on O is a family of subsets of O that are incomparable under inclusion. Given a collection S of clutters on O and another clutter ¿ on O, we study the problem of approximating and decomposing ¿ in terms of the clutters in S. We want to guarantee when these approximations exist not only for a single element ¿, but for all ¿ that belong to a family of clutters . We use the lattice structure of the collection of clutters to show that the existence of such approximations and decompositions for every clutter ¿ is equivalent to the fact that S contains a given family of irreducible elements determined by S and . We explicitly compute these irreducible families in some cases and apply our results to clutters arising from discrete objects such as matroids, graphs and secret sharing schemes., This work was partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under projects PGC2018-095471-B-I00 and PID2020-113082GB-I00; by AGAUR, Generalitat de Catalunya, from the Catalan Government under projects SGR-Cat 2021 00595 and SGR-Cat 2021 00585; by Universitat Politècnica de Catalunya under funds AGRUPUPC., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Grafs aleatoris amb una seqüència de graus donada

  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
Des de l’aparició de la noció de xarxes complexes, els grafs aleatoris han resultat una eina fonamental per modelar-les i estudiar-les. En aquest article tractarem l’estudi dels grafs aleatoris amb una seqüència de graus donada, en què el grau de cada vèrtex és fixat a priori per després triar una instància aleatòria que respecti aquestes restriccions. El nostre objectiu és introduir en aquest tema el lector que no hi està familiaritzat, enunciant els resultats més rellevants en l’àrea i explicant perquè són certs, sense donar-ne proves rigoroses., L’autor d’aquest article ha rebut suport de l’Agencia Estatal de Investigación a través del projecte PID2020-113082GB-I00, del projecte RED2022-134947-T, i del programa Severo Ochoa i María de Maeztu per a centres i unitats d’excel. lència en R + D (CEX2020-001084-M)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Quantum error-correcting codes and their geometries

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Centelles Tarrés, Aina
  • Huber, Felix
This is an expository article aiming to introduce the reader to the underlying mathematics and geometry of quantum error correction. Information stored on quantum particles is subject to noise and interference from the environment. Quantum error-correcting codes allow the negation of these effects in order to successfully restore the original quantum information. We briefly describe the necessary quantum-mechanical background to be able to understand how quantum error correction works. We go on to construct quantum codes: firstly qubit stabilizer codes, then qubit non-stabilizer codes, and finally codes with a higher local dimension. We will delve into the geometry of these codes. This allows one to deduce the parameters of the code efficiently, deduce the inequivalence between codes that have the same parameters, and presents a useful tool in deducing the feasibility of certain parameters. We also include sections on quantum maximum distance separable codes and the quantum MacWilliams identities, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On minimum vertex bisection of random d-regular graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Yasar Diner, Oznur
  • Serna Iglesias, María José|||0000-0001-9729-8648
  • Serra Albó, Oriol|||0000-0001-8561-4631
Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d-regular graphs, for constant values of d. Our approach is based on analyzing a greedy algorithm by using the differential equation method. In this way, we obtain the first known non-trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald (2014) [30]., J. Díaz and M. Serna were partially supported by the Spanish Agencia Estatal de Investigación under project MOTION, PID2020-112581 GB-C21. O.Y. Diner was partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra research was supported by the Spanish Agencia Estatal de Investigación under project CONTREWA, PID2020-113082 GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Rankings in directed configuration models with heavy tailed in-degrees

  • Cai, Xing Shi
  • Caputo, Pietro
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
  • Quattropani, Matteo
We consider the extremal values of the stationary distribution of sparse directed random graphs with given degree sequences and their relation to the extremal values of the in-degree sequence. The graphs are generated by the directed configuration model. Under the assumption of bounded ( 2 + ¿ ) -moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have a power-law behavior, we show that the extremal values of the stationary distribution also have a power-law behavior with the same index. In the same setting, we prove that these results extend to the PageRank scores of the random digraph, thus confirming a version of the so-called power-law hypothesis. Along the way we establish several facts about the model, including the mixing time cutoff and the characterization of the typical values of the stationary distribution, which were previously obtained under the assumption of bounded in-degrees., The third author was supported by the Spanish Agencia Estatal de Investigación under projects MTM2017-82166-P and PID2020-113082GB-I00 and by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M).
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
We prove that the cyclic and constacyclic codes constructed by Grassl and Rötteler in International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015) are generalised Reed–Solomon codes. This note can be considered as an addendum to Grassl and Rötteler International Symposium on Information Theory (ISIT), pp 1104–1108 (2015). It can also be considered as an appendix to Ball and Vilar IEEE Trans Inform Theory 68:3796–3805, (2022) where Conjecture 11 of International Symposium on Information Theory (ISIT), pp 1104–1108 (2015), which was stated for Grassl–Rötteler codes, is proven for generalised Reed–Solomon codes. The content of this note, together with IEEE Trans Inform Theory 68:3796–3805, (2022) therefore implies that Conjecture 11 from International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015) is true., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the chromatic number of powers of subdivisions of graphs

  • Anastos, Michael
  • Boyadzhiyska, Simona
  • Rathke, Silas
  • Rué Perna, Juan José|||0000-0002-6420-3179
For a given graph G = (V, E), we define its nth subdivision as the graph obtained from G by replacing every edge by a path of length n. We also define the mth power of G as the graph on vertex set V where we connect every pair of vertices at distance at most m in G. In this paper, we study the chromatic number of powers of subdivisions of graphs and resolve the case m = n asymptotically. In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in the case m = n = 3 in a strong sense., M.A.: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413 . S.B.: The research leading to these results was supported by EPSRC, UK, grant no. EP/V048287/1. There are no additional data beyond that contained within the main manuscript. S.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). J.R. acknowledges the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033, Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D, Spain (CEX2020-001084-M)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On homogeneous matroid ports

  • Martí Farré, Jaume|||0000-0002-2596-5971
  • Mier Vinué, Anna de|||0000-0002-2817-7807
A matroid port is a clutter (antichain of sets) determined by the collection of circuits of a matroid that contain a fixed point. We study the problem of determining matroid ports all whose elements have the same size h. This problem has been studied from the cryptographic perspective and it is related to an analogous problem in matroid theory. We give some general results and then focus on the binary case. We recast some known results and find all 4-homogeneous binary matroid ports., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The diameter of the directed configuration model

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We show that the diameter of the directed configuration model with n vertices rescaled by log n converges in probability to a constant. Our assumptions are the convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment. Our result extends previous results on the diameter of the model and applies to many other random directed graphs. Nous montrons que le diamètre du modèle de configuration dirigé avec n sommets renormalisé par log n converge en probabilité vers une constante. Nos hypothèses sont la convergence en loi des degrés entrant et sortant d’un sommet uniformément choisi, et celles en moments d’ordre 1 et d’ordre 2. Notre résultat étend les résultats précédents sur le diamètre du modèle et s’applique à de nombreux autres graphes orientés aléatoires., This work is supported by the Agencia Estatal de Investigación (MCIN/AEI) through the a Proyecto I+D+i 2020 (PID2020-113082GB-I00), through the Marie Skłodowska-Curie Research and Innovation Staff Exchange grant RandNet (MSCA-RISE-2020-101007705) and through the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Speeding up random walk mixing by starting from a uniform vertex

  • Espuny Díaz, Alberto
  • Morris, Patrick
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
  • Serra Albó, Oriol|||0000-0001-8561-4631
The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to the slow diffusion caused by these bottlenecks. In this paper we provide a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order (log n) 2, speeding up the mixing to order log n. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erdos-Rényi graph is logarithmic., This research has been supported by the Spanish Agencia Estatal de Investigación under projects PID2020-113082GB-I00 and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). Alberto Espuny Díaz was partially supported by the Carl Zeiss Foundation and by DFG (German Research Foundation) grant PE 2299/3-1. Patrick Morris was supported by the DFG Walter Benjamin program – project number 504502205, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Diner, Oznur Y.
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Serna Iglesias, María José|||0000-0001-9729-8648
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The equivalence of linear codes implies semi-linear equivalence

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The multicolored graph realization problem

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Yasar Diner, Oznur
  • Serna Iglesias, María José|||0000-0001-9729-8648
  • Serra Albó, Oriol|||0000-0001-8561-4631
We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G, φ), i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G, φ) with a cluster graph (Gφ ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G[S] coincides with Gφ . The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [1]-hard when parameterized by the number of colors. Thus, MGR remains W [1]-hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [1]-hard when parameterized by any graph parameter on Gφ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of Gφ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when Gφ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size ., J. Díaz and M. Serna are partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2017-SGR-786 (ALBCOM). Ö. Y. Diner is partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Agencia Estatal de Investigación under grant PID2020-113082GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Capítulo o parte de un libro (BookPart)

Tutte uniqueness and Tutte equivalence

  • Bonin, Joseph E.
  • Mier Vinué, Anna de|||0000-0002-2817-7807
This chapter considers graphs or matroids that have the same Tutte polynomial, as well as graphs or matroids that, up to isomorphism, are distinguished from all others by their Tutte polynomial. We call the former Tutte equivalent, and the latter Tutte unique. Tutte invariants (data that the Tutte polynomial contains). Operations that preserve Tutte uniqueness or equivalence. Connections between the graph and matroid Tutte-uniqueness problems. Constructions of large families of Tutte-equivalent graphs and matroids. Tutte-unique graphs and matroids, and characterizations of some of these graphs and matroids by Tutte invariants. Related lines of research., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Short synchronizing words for random automata

  • Chapuy, Guillaume
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ¿ of such length, and a state v0, such that ¿ sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykula [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ¿ we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p. Our proof introduces the concept of ¿-trees, for a word ¿, that is, automata in which the ¿-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ¿-tree for some word ¿ of length at most (1 + e) log2(n), for any e > 0. The existence of the (random) word ¿ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Enumeration of chordal planar graphs and maps

  • Castellví Foguet, Jordi
  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Requile, Clement|||0000-0002-7689-7972
We determine the number of labelled chordal planar graphs with n vertices, which is asymptotically for a constant and . We also determine the number of rooted simple chordal planar maps with n edges, which is asymptotically , where , , and s is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from by repeatedly adding vertices adjacent to an existing triangular face., We gratefully acknowledge earlier discussions on this project with Erkan Narmanli. M.N. was supported by grants MTM2017-82166-P and PID2020-113082GB-I00, the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). C.R. was supported by the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency for management of university and research grants), and the grant PID2020-113082GB-I00 of the Spanish Ministry of Science and Innovation., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Marked graphs and the chromatic symmetric function

  • Aliste Prieto, José
  • Mier Vinué, Anna de|||0000-0002-2817-7807
  • Orellana, Rosa
  • Zamora Ponce, José
The main result of this paper is the introduction of marked graphs and the marked graph polynomials ( -polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the -polynomial, introduced by Noble and Welsh, and a specialization of the -polynomial, introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the -polynomial, which we call the -polynomial. Furthermore, we present an efficient algorithm for computing the chromatic symmetric function of a graph in the star basis of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 are reconstructible from its chromatic symmetric function., JAP was partially supported by FONDECYT REGULAR 1160975 CONICYT Chile. AdM was partially supported by PID2020-113082GB-I00 funded by MCIN/AEI. RO was partially supported by NSF grant DMS–300512. JZ was partially supported by FONDECYT REGULAR 1180994 CONICYT Chile., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The rado multiplicity problem in vector spaces over finite fields

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Spiegel, Christoph
We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in $2$-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al.~\cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf~\cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov~\cite{razborov2007flag}., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Stabiliser codes over fields of even order

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Moreno Martínez, Edgar
  • Simoens, Robin Nicolas|||0000-0001-7398-3085
© 2024 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We prove that the natural isomorphism F2h ~= F h 2 induces a bijection between stabilizer codes on n quqits with local dimension q = 2h and binary stabilizer codes on hn qubits. This allows us to describe these codes geometrically: a stabilizer code over a field of even order corresponds to a so-called quantum set of symplectic polar spaces. Moreover, equivalent stabilizer codes have a similar geometry, which can be used to prove the uniqueness of a [[4, 0, 3]]4 stabilizer code and the nonexistence of both a [[7, 1, 4]]4 and an [[8, 0, 5]]4 stabilizer code., The work of Simeon Ball was supported in part by MCIN/AEI/10.13039/501100011033 under Grant PID2020-113082GB-I00 and in part by the Spanish Ministry of Science and Innovation. The work of Edgar Moreno was supported in part by the Higher Interdisciplinary Training Center (CFIS)-Universitat Politècnica de Catalunya (UPC) and in part by SANTANDER-UPC INITIAL RESEARCH GRANTS (INIREC). The work of Robin Simoens was supported by the Research Foundation Flanders under Grant 11PG724N.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Largest component of subcritical random graphs with given degree sequence

  • Coulson, Matthew John
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We study the size of the largest component of two models of random graphs with prescribed degree sequence, the configuration model (CM) and the uniform model (UM), in the (barely) subcritical regime. For the CM, we give upper bounds that are asymptotically tight for certain degree sequences. These bounds hold under mild conditions on the sequence and improve previous results of Hatami and Molloy on the barely subcritical regime. For the UM, we give weaker upper bounds that are tight up to logarithmic terms but require no assumptions on the degree sequence. In particular, the latter result applies to degree sequences with infinite variance in the subcritical regime., M.C. was supported by the FPI grant PRE2018-083621 associated to the project MTM2017-82166-P from the Spanish Ministerio de Economía y Competitividad. G.P was supported by the Spanish Agencia Estatal de Investigación under projects MTM2017-82166-P and PID2020-113082GB-I00, and by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M).
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

De la teoria de grafs clàssica a l’anàlisi de les grans xarxes

  • Rué Perna, Juan José|||0000-0002-6420-3179
Actualment la teoria de grafs té un paper fonamental tant en les matemà-tiques pures com en les seves aplicacions en moltes branques del coneixement. Enaquest article recorrerem l’evolució de l’àrea de recerca partint del seu naixementi passant per les grans descobertes de la disciplina, especialment les relatives a lainteracció amb la noció d’atzar. Finalment, el nostre recorregut finalitzarà discutintalgunes de les tendències actuals de la teoria, que cerquen encabir la noció de discret(inherent a la teoria de grafs) dins del reialme de les matemàtiques contínues ambl’objectiu d’afrontar, entre d’altres grans reptes, l’estudi sistemàtic de les grans xarxesexistents al món real., L’autor agraeix el suport delsprojectes de recerca MTM2017-82166-P, PID2020-113082GB-I00, de la xarxaRISE-EU «RandNet» (referència 101007705) i del programa Severo Ochoa i Maríade Maeztu per a centres i unitats d’excel.lència en R+D (referència CEX2020-001084-M)., Peer Reviewed, Objectius de Desenvolupament Sostenible::4 - Educació de Qualitat
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Percolation on dense random graphs with given degrees

  • Lichev, Lyuben
  • Mitsche, Dieter
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
In this paper, we study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a given degree sequence, and then bond percolation is applied. Far from being able to classify all such degree sequences, we exhibit several new threshold phenomena for the order of the largest component in terms of both sources of randomness. We also provide an example of a degree sequence for which the order of the largest component undergoes an unbounded number of jumps in terms of the percolation parameter, giving rise to a behavior that cannot be observed without percolation., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Normal limiting distributions for systems of linear equations in random sets

  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Wotzel, Maximilian
We consider the binomial random set model where each element in is chosen independently with probability . We show that for essentially all regimes of p and very general conditions for a matrix A and a column vector b, the count of specific integer solutions to the system of linear equations with the entries of x in follows a (conveniently rescaled) normal limiting distribution. This applies among others to the number of solutions with every variable having a different value, as well as to a broader class of so-called non-trivial solutions in homogeneous strictly balanced systems. Our proof relies on the delicate linear algebraic study both of the subjacent matrices and the corresponding ranks of certain submatrices, together with the application of the method of moments in probability theory., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Enumeration of labelled 4-regular planar graphs II: asymptotics

  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Requile, Clement|||0000-0002-7689-7972
  • Rué Perna, Juan José|||0000-0002-6420-3179
This work is a follow-up of the article (Noy et al., 2019), where the authors solved the problem of counting labelled 4-regular planar graphs. In this paper, we obtain a precise asymptotic estimate for the number of labelled 4-regular planar graphs on vertices. Our estimate is of the form , where is a constant and is the radius of convergence of the generating function , and conforms to the universal pattern obtained previously in the enumeration of several classes of planar graphs. In addition to analytic methods, our solution needs intensive use of computer algebra in order to deal with large systems of multivariate polynomial equations. We also obtain asymptotic estimates for the number of 2- and 3-connected 4-regular planar graphs, and for the number of 4-regular simple maps, both connected and 2-connected., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The lonely runner conjecture turns 60

  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
  • Serra Albó, Oriol|||0000-0001-8561-4631
The Lonely Runner Conjecture originated in Diophantine approximation is turning 60. Even if the conjecture is still widely open, the flow of partial results, innovative tools and connections to different problems and applications has been steady on its long life. This survey attempts to give a panoramic view of the status of the problem, trying to highlight the contributions of the many papers that it has originated., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Enumeration of rooted 3-connected bipartite planar maps, Énumération des cartes planaires enracinées biparties et 3-connexes

  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Requile, Clement|||0000-0002-7689-7972
  • Rué Perna, Juan José|||0000-0002-6420-3179
We provide the first solution to the problem of counting rooted 3-connected bipartite planar maps. Our starting point is the enumeration of bicoloured planar maps according to the number of edges and monochromatic edges, following Bernardi and Bousquet-Mélou [J. Comb. Theory Ser. B, 101 (2011), 315–377]. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicoloured maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form t n-5/2¿ n, where ¿ = ¿ -1 ˜ 2.40958 and ¿ ˜ 0.41501 is an algebraic number of degree 10., The authors acknowledge the financial support of the Spanish State Research Agency through projects MTM2017-82166-P, PID2020-113082GB-I00, and the Marie Curie RISE research network ’RandNet’ MSCA-RISE-2020-101007705. Additionally, M.N. and J.R. acknowledge support from the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence (CEX2020-001084-M), and C.R. acknowledges support from the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency for management of university and research grants)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Minimum stationary values of sparse random directed graphs

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution (uniqueness regime). We show that the minimum positive stationary value is whp n-(1+C+o(1)) for some constant C=0 determined by the degree distribution, answering a question raised by Bordenave, Caputo and Salez (Probab. Theory Related Fields 170 (2018) 933–960). In particular, C is the competing combination of two factors: (1) the contribution of atypically “thin” in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. Additionally, we give estimates for the expected lower tail of the empirical stationary distribution. As a by-product of our proof, we obtain that the hitting and the cover time are both n1+C+o(1) whp. Our results are in sharp contrast to those of Caputo and Quattropani (Probab. Theory Related Fields 178 (2020) 1011–1066) who showed that under the additional condition of minimum in-degree at least 2 (ergodicity regime), stationary values only have logarithmic fluctuations around n-1., We would like to thanks Pietro Caputo and Matteo Quattropani for insightful discussions on the topic. We are also grateful to the three anonymous reviewers, whose insightful comments have greatly contributed to improving this paper. G.P. was supported by the grants PID2020-113082GB-I00, PID2023-147202NB-I00, PCI2024-155080-2 and the Programme Severo Ochoa y María de Maeztu por Centros y Unidades de Excelencia en I&D (CEX2020-001084-M), all of them funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Product-free sets in the free group

  • Ortega Sánchez Colomer, Miquel|||0009-0003-4043-7266
  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Serra Albó, Oriol|||0000-0001-8561-4631
We prove that product-free sets of the free group over a finite alphabet have max-imum density1/2with respect to the natural measure that assigns total weight oneto each set of irreducible words of a given length. This confirms a conjecture ofLeader, Letzter, Narayanan and Walters. In more general terms, we actually provethat stronglyk-product-free sets have maximum density1/kin terms of the saidmeasure. The bounds are tight., We acknowledge the support of the grants MTM2017-82166-P, PID2020-113082GB-I00,and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellencein R&D (CEX2020-001084-M). Miquel Ortega also acknowledges the support of the FPIgrant PRE2021-099120., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On additive MDS codes with linear projections

  • Adriaensen, Sam
  • Ball, Simeon Michael
We support some evidence that a long additive MDS code over a finite field must be equivalent to a linear code. More precisely, let C be an -linear MDS code over . If , , , and C has three coordinates from which its projections are equivalent to -linear codes, we prove that C itself is equivalent to an -linear code. If , , and there are two disjoint subsets of coordinates whose combined size is at most from which the projections of C are equivalent to -linear codes, we prove that C is equivalent to a code which is linear over a larger field than ., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Random cubic planar maps

  • Drmota, Michael
  • Noy Serrano, Marcos
  • Requile, Clement
  • Rué Perna, Juan José
We analyse uniform random cubic rooted planar maps and obtain limiting distributions for several parameters of interest. From the enumerative point of view, we present a unified approach for the enumeration of several classes of cubic planar maps, which allow us to recover known results in a more general and transparent way. This approach allows us to obtain new enumerative results. Concerning random maps, we first obtain the distribution of the degree of the root face, which has an exponential tail as for other classes of random maps. Our main result is a limiting map-Airy distribution law for the size of the largest block L, whose expectation is asymptotically n/v3 in a random cubic map with n+ 2 faces. We prove analogous results for the size of the largest cubic block, obtained from L by erasing all vertices of degree two, and for the size of the largest 3-connected component, whose expected values are respectively n/2 and n/4. To obtain these results we need to analyse a new type of composition scheme which has not been treated by Banderier et al. [Random Structures Algorithms 2001]., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On minimum vertex bisection of random d-regular graphs

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that have a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d-regular graphs, for constant values of d. Our approach is based on analyzing a greedy algorithm by using the differential equation method. In this way, we obtain the first known non-trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald (2014) [30]., J. Díaz and M. Serna were partially supported by the Spanish Agencia Estatal de Investigación under project MOTION, PID2020-112581 GB-C21. O.Y. Diner was partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra research was supported by the Spanish Agencia Estatal de Investigación under project CONTREWA, PID2020-113082 GB-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Product-free sets in the free group

  • Ortega Sánchez Colomer, Miquel
  • Rué Perna, Juan José
  • Serra Albó, Oriol
We prove that product-free sets of the free group over a finite alphabet have max-imum density1/2with respect to the natural measure that assigns total weight oneto each set of irreducible words of a given length. This confirms a conjecture ofLeader, Letzter, Narayanan and Walters. In more general terms, we actually provethat stronglyk-product-free sets have maximum density1/kin terms of the saidmeasure. The bounds are tight., We acknowledge the support of the grants MTM2017-82166-P, PID2020-113082GB-I00,and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellencein R&D (CEX2020-001084-M). Miquel Ortega also acknowledges the support of the FPIgrant PRE2021-099120., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The lonely runner conjecture turns 60

  • Perarnau Llobet, Guillem
  • Serra Albó, Oriol
The Lonely Runner Conjecture originated in Diophantine approximation is turning 60. Even if the conjecture is still widely open, the flow of partial results, innovative tools and connections to different problems and applications has been steady on its long life. This survey attempts to give a panoramic view of the status of the problem, trying to highlight the contributions of the many papers that it has originated., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Largest component of subcritical random graphs with given degree sequence

  • Coulson, Matthew John
  • Perarnau Llobet, Guillem
We study the size of the largest component of two models of random graphs with prescribed degree sequence, the configuration model (CM) and the uniform model (UM), in the (barely) subcritical regime. For the CM, we give upper bounds that are asymptotically tight for certain degree sequences. These bounds hold under mild conditions on the sequence and improve previous results of Hatami and Molloy on the barely subcritical regime. For the UM, we give weaker upper bounds that are tight up to logarithmic terms but require no assumptions on the degree sequence. In particular, the latter result applies to degree sequences with infinite variance in the subcritical regime., M.C. was supported by the FPI grant PRE2018-083621 associated to the project MTM2017-82166-P from the Spanish Ministerio de Economía y Competitividad. G.P was supported by the Spanish Agencia Estatal de Investigación under projects MTM2017-82166-P and PID2020-113082GB-I00, and by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Griesmer type bounds for additive codes over finite fields, integral and fractional MDS codes

  • Ball, Simeon Michael
  • Lavrauw, Michel
  • Popatia, Tabriz Arun Avery
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10623-024-01519-2, In this article we prove Griesmer type bounds for additive codes over finite fields. These new bounds give upper bounds on the length of maximum distance separable (MDS) codes, codes which attain the Singleton bound. We will also consider codes to be MDS if they attain the fractional Singleton bound, due to Huffman. We prove that this bound in the fractional case can be obtained by codes whose length surpasses the length of the longest known codes in the integral case. For small parameters, we provide exhaustive computational results for additive MDS codes, by classifying the corresponding (fractional) subspace-arcs. This includes a complete classification of fractional additive MDS codes of size 243 over the field of order 9., The first and third author are supported by the Spanish Ministry of Science, Innovation and Universities grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033 and grant PID2023-147202NB-I00, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Polynomials for marked graphs and the chromatic symmetric function

Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Enumeration of rooted 3-connected bipartite planar maps, Énumération des cartes planaires enracinées biparties et 3-connexes

  • Noy Serrano, Marcos
  • Requile, Clement
  • Rué Perna, Juan José
We provide the first solution to the problem of counting rooted 3-connected bipartite planar maps. Our starting point is the enumeration of bicoloured planar maps according to the number of edges and monochromatic edges, following Bernardi and Bousquet-Mélou [J. Comb. Theory Ser. B, 101 (2011), 315–377]. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicoloured maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form t n-5/2¿ n, where ¿ = ¿ -1 ˜ 2.40958 and ¿ ˜ 0.41501 is an algebraic number of degree 10., The authors acknowledge the financial support of the Spanish State Research Agency through projects MTM2017-82166-P, PID2020-113082GB-I00, and the Marie Curie RISE research network ’RandNet’ MSCA-RISE-2020-101007705. Additionally, M.N. and J.R. acknowledge support from the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence (CEX2020-001084-M), and C.R. acknowledges support from the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency for management of university and research grants)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Short synchronizing words for random automata

  • Chapuy, Guillaume
  • Perarnau Llobet, Guillem
We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length with high probability (w.h.p.). That is to say, w.h.p. there exists a word ¿ of such length, and a state v0, such that ¿ sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykula [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(n log3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ¿ we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p. Our proof introduces the concept of ¿-trees, for a word ¿, that is, automata in which the ¿-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a ¿-tree for some word ¿ of length at most (1 + e) log2(n), for any e > 0. The existence of the (random) word ¿ is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Enumeration of labelled 4-regular planar graphs II: asymptotics

  • Noy Serrano, Marcos
  • Requile, Clement
  • Rué Perna, Juan José
This work is a follow-up of the article (Noy et al., 2019), where the authors solved the problem of counting labelled 4-regular planar graphs. In this paper, we obtain a precise asymptotic estimate for the number of labelled 4-regular planar graphs on vertices. Our estimate is of the form , where is a constant and is the radius of convergence of the generating function , and conforms to the universal pattern obtained previously in the enumeration of several classes of planar graphs. In addition to analytic methods, our solution needs intensive use of computer algebra in order to deal with large systems of multivariate polynomial equations. We also obtain asymptotic estimates for the number of 2- and 3-connected 4-regular planar graphs, and for the number of 4-regular simple maps, both connected and 2-connected., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

The rado multiplicity problem in vector spaces over finite fields

  • Rué Perna, Juan José
  • Spiegel, Christoph
We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in $2$-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al.~\cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf~\cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov~\cite{razborov2007flag}., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Grafs aleatoris amb una seqüència de graus donada

  • Perarnau Llobet, Guillem
Des de l’aparició de la noció de xarxes complexes, els grafs aleatoris han resultat una eina fonamental per modelar-les i estudiar-les. En aquest article tractarem l’estudi dels grafs aleatoris amb una seqüència de graus donada, en què el grau de cada vèrtex és fixat a priori per després triar una instància aleatòria que respecti aquestes restriccions. El nostre objectiu és introduir en aquest tema el lector que no hi està familiaritzat, enunciant els resultats més rellevants en l’àrea i explicant perquè són certs, sense donar-ne proves rigoroses., L’autor d’aquest article ha rebut suport de l’Agencia Estatal de Investigación a través del projecte PID2020-113082GB-I00, del projecte RED2022-134947-T, i del programa Severo Ochoa i María de Maeztu per a centres i unitats d’excel. lència en R + D (CEX2020-001084-M)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Speeding up random walk mixing by starting from a uniform vertex

  • Espuny Díaz, Alberto
  • Morris, Patrick
  • Perarnau Llobet, Guillem
  • Serra Albó, Oriol
The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to the slow diffusion caused by these bottlenecks. In this paper we provide a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order (log n) 2, speeding up the mixing to order log n. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erdos-Rényi graph is logarithmic., This research has been supported by the Spanish Agencia Estatal de Investigación under projects PID2020-113082GB-I00 and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). Alberto Espuny Díaz was partially supported by the Carl Zeiss Foundation and by DFG (German Research Foundation) grant PE 2299/3-1. Patrick Morris was supported by the DFG Walter Benjamin program – project number 504502205, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Quantum error-correcting codes and their geometries

  • Ball, Simeon Michael
  • Centelles Tarrés, Aina
  • Huber, Felix
This is an expository article aiming to introduce the reader to the underlying mathematics and geometry of quantum error correction. Information stored on quantum particles is subject to noise and interference from the environment. Quantum error-correcting codes allow the negation of these effects in order to successfully restore the original quantum information. We briefly describe the necessary quantum-mechanical background to be able to understand how quantum error correction works. We go on to construct quantum codes: firstly qubit stabilizer codes, then qubit non-stabilizer codes, and finally codes with a higher local dimension. We will delve into the geometry of these codes. This allows one to deduce the parameters of the code efficiently, deduce the inequivalence between codes that have the same parameters, and presents a useful tool in deducing the feasibility of certain parameters. We also include sections on quantum maximum distance separable codes and the quantum MacWilliams identities, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

De la teoria de grafs clàssica a l’anàlisi de les grans xarxes

  • Rué Perna, Juan José
Actualment la teoria de grafs té un paper fonamental tant en les matemà-tiques pures com en les seves aplicacions en moltes branques del coneixement. Enaquest article recorrerem l’evolució de l’àrea de recerca partint del seu naixementi passant per les grans descobertes de la disciplina, especialment les relatives a lainteracció amb la noció d’atzar. Finalment, el nostre recorregut finalitzarà discutintalgunes de les tendències actuals de la teoria, que cerquen encabir la noció de discret(inherent a la teoria de grafs) dins del reialme de les matemàtiques contínues ambl’objectiu d’afrontar, entre d’altres grans reptes, l’estudi sistemàtic de les grans xarxesexistents al món real., L’autor agraeix el suport delsprojectes de recerca MTM2017-82166-P, PID2020-113082GB-I00, de la xarxaRISE-EU «RandNet» (referència 101007705) i del programa Severo Ochoa i Maríade Maeztu per a centres i unitats d’excel.lència en R+D (referència CEX2020-001084-M)., Peer Reviewed, Objectius de Desenvolupament Sostenible::4 - Educació de Qualitat, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the chromatic number of powers of subdivisions of graphs

  • Anastos, Michael
  • Boyadzhiyska, Simona
  • Rathke, Silas
  • Rué Perna, Juan José
For a given graph G = (V, E), we define its nth subdivision as the graph obtained from G by replacing every edge by a path of length n. We also define the mth power of G as the graph on vertex set V where we connect every pair of vertices at distance at most m in G. In this paper, we study the chromatic number of powers of subdivisions of graphs and resolve the case m = n asymptotically. In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in the case m = n = 3 in a strong sense., M.A.: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413 . S.B.: The research leading to these results was supported by EPSRC, UK, grant no. EP/V048287/1. There are no additional data beyond that contained within the main manuscript. S.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). J.R. acknowledges the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033, Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D, Spain (CEX2020-001084-M)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The equivalence of linear codes implies semi-linear equivalence

  • Ball, Simeon Michael
  • Dixon, James
The version of record is available online at: 10.1007/s10623-022-01055-x, We prove that if two linear codes are equivalent then they are semi-linearly equivalent. We also prove that if two additive MDS codes over a field are equivalent then they are additively equivalent., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Minimum stationary values of sparse random directed graphs

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem
We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution (uniqueness regime). We show that the minimum positive stationary value is whp n-(1+C+o(1)) for some constant C=0 determined by the degree distribution, answering a question raised by Bordenave, Caputo and Salez (Probab. Theory Related Fields 170 (2018) 933–960). In particular, C is the competing combination of two factors: (1) the contribution of atypically “thin” in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically “light” trajectories, controlled by large deviation rate functions. Additionally, we give estimates for the expected lower tail of the empirical stationary distribution. As a by-product of our proof, we obtain that the hitting and the cover time are both n1+C+o(1) whp. Our results are in sharp contrast to those of Caputo and Quattropani (Probab. Theory Related Fields 178 (2020) 1011–1066) who showed that under the additional condition of minimum in-degree at least 2 (ergodicity regime), stationary values only have logarithmic fluctuations around n-1., We would like to thanks Pietro Caputo and Matteo Quattropani for insightful discussions on the topic. We are also grateful to the three anonymous reviewers, whose insightful comments have greatly contributed to improving this paper. G.P. was supported by the grants PID2020-113082GB-I00, PID2023-147202NB-I00, PCI2024-155080-2 and the Programme Severo Ochoa y María de Maeztu por Centros y Unidades de Excelencia en I&D (CEX2020-001084-M), all of them funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On additive MDS codes over small fields

  • Ball, Simeon Michael
  • Gamboa Jimenez, Gonzalo
  • Lavrauw, Michel
Let $ C $ be a $ (n,q^{2k},n-k+1)_{q^2} $ additive MDS code which is linear over $ {\mathbb F}_q $. We prove that if $ n \geq q+k $ and $ k+1 $ of the projections of $ C $ are linear over $ {\mathbb F}_{q^2} $ then $ C $ is linear over $ {\mathbb F}_{q^2} $. We use this geometrical theorem, other geometric arguments and some computations to classify all additive MDS codes over $ {\mathbb F}_q $ for $ q \in \{4,8,9\} $. We also classify the longest additive MDS codes over $ {\mathbb F}_{16} $ which are linear over $ {\mathbb F}_4 $. In these cases, the classifications not only verify the MDS conjecture for additive codes, but also confirm there are no additive non-linear MDS codes which perform as well as their linear counterparts. These results imply that the quantum MDS conjecture holds for $ q \in \{ 2,3\} $., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The diameter of the directed configuration model

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem
We show that the diameter of the directed configuration model with n vertices rescaled by log n converges in probability to a constant. Our assumptions are the convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment. Our result extends previous results on the diameter of the model and applies to many other random directed graphs. Nous montrons que le diamètre du modèle de configuration dirigé avec n sommets renormalisé par log n converge en probabilité vers une constante. Nos hypothèses sont la convergence en loi des degrés entrant et sortant d’un sommet uniformément choisi, et celles en moments d’ordre 1 et d’ordre 2. Notre résultat étend les résultats précédents sur le diamètre du modèle et s’applique à de nombreux autres graphes orientés aléatoires., This work is supported by the Agencia Estatal de Investigación (MCIN/AEI) through the a Proyecto I+D+i 2020 (PID2020-113082GB-I00), through the Marie Skłodowska-Curie Research and Innovation Staff Exchange grant RandNet (MSCA-RISE-2020-101007705) and through the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Marked graphs and the chromatic symmetric function

  • Aliste Prieto, José
  • Mier Vinué, Anna de
  • Orellana, Rosa
  • Zamora Ponce, José
The main result of this paper is the introduction of marked graphs and the marked graph polynomials ( -polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the -polynomial, introduced by Noble and Welsh, and a specialization of the -polynomial, introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the -polynomial, which we call the -polynomial. Furthermore, we present an efficient algorithm for computing the chromatic symmetric function of a graph in the star basis of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 are reconstructible from its chromatic symmetric function., JAP was partially supported by FONDECYT REGULAR 1160975 CONICYT Chile. AdM was partially supported by PID2020-113082GB-I00 funded by MCIN/AEI. RO was partially supported by NSF grant DMS–300512. JZ was partially supported by FONDECYT REGULAR 1180994 CONICYT Chile., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On homogeneous matroid ports

  • Martí Farré, Jaume
  • Mier Vinué, Anna de
A matroid port is a clutter (antichain of sets) determined by the collection of circuits of a matroid that contain a fixed point. We study the problem of determining matroid ports all whose elements have the same size h. This problem has been studied from the cryptographic perspective and it is related to an analogous problem in matroid theory. We give some general results and then focus on the binary case. We recast some known results and find all 4-homogeneous binary matroid ports., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Rainbow connectivity of multilayered random geometric graphs

  • Díaz Cort, Josep
  • Diner, Oznur Y.
  • Serra Albó, Oriol
  • Serna Iglesias, María José
An edge-colored multigraph G is rainbow connected if every pair of vertices is joined by at least one rainbow path, i.e., a path where no two edges are of the same color. In the context of multilayered networks, we introduce the notion of multilayered random geometric graphs, from h = 2 independent random geometric graphs G(n,r) on the unit square. We define an edge-coloring by coloring the edges according to the copy of G(n,r) they belong to and study the rainbow connectivity of the resulting edge-colored multigraph. We show that r(n) = lnn nh-1 1/2h , is a threshold of the radius for the property of being rainbow connected. This complements the known analogous results for the multilayered graphs defined on the Erdos–Rényi random model., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The multicolored graph realization problem

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G, φ), i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G, φ) with a cluster graph (Gφ ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G[S] coincides with Gφ . The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [1]-hard when parameterized by the number of colors. Thus, MGR remains W [1]-hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [1]-hard when parameterized by any graph parameter on Gφ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of Gφ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when Gφ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size ., J. Díaz and M. Serna are partially supported by funds from the Spanish Agencia Estatal de Investigación under grant PID2020-112581GB-C21 (MOTION), and from AGAUR under grant 2017-SGR-786 (ALBCOM). Ö. Y. Diner is partially supported by the Scientific and Technological Research Council Tübitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Agencia Estatal de Investigación under grant PID2020-113082GB-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Stabiliser codes over fields of even order

  • Ball, Simeon Michael
  • Moreno Martínez, Edgar
  • Simoens, Robin Nicolas
© 2024 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., We prove that the natural isomorphism F2h ~= F h 2 induces a bijection between stabilizer codes on n quqits with local dimension q = 2h and binary stabilizer codes on hn qubits. This allows us to describe these codes geometrically: a stabilizer code over a field of even order corresponds to a so-called quantum set of symplectic polar spaces. Moreover, equivalent stabilizer codes have a similar geometry, which can be used to prove the uniqueness of a [[4, 0, 3]]4 stabilizer code and the nonexistence of both a [[7, 1, 4]]4 and an [[8, 0, 5]]4 stabilizer code., The work of Simeon Ball was supported in part by MCIN/AEI/10.13039/501100011033 under Grant PID2020-113082GB-I00 and in part by the Spanish Ministry of Science and Innovation. The work of Edgar Moreno was supported in part by the Higher Interdisciplinary Training Center (CFIS)-Universitat Politècnica de Catalunya (UPC) and in part by SANTANDER-UPC INITIAL RESEARCH GRANTS (INIREC). The work of Robin Simoens was supported by the Research Foundation Flanders under Grant 11PG724N., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

Tutte uniqueness and Tutte equivalence

  • Bonin, Joseph E.
  • Mier Vinué, Anna de
This chapter considers graphs or matroids that have the same Tutte polynomial, as well as graphs or matroids that, up to isomorphism, are distinguished from all others by their Tutte polynomial. We call the former Tutte equivalent, and the latter Tutte unique. Tutte invariants (data that the Tutte polynomial contains). Operations that preserve Tutte uniqueness or equivalence. Connections between the graph and matroid Tutte-uniqueness problems. Constructions of large families of Tutte-equivalent graphs and matroids. Tutte-unique graphs and matroids, and characterizations of some of these graphs and matroids by Tutte invariants. Related lines of research., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Rankings in directed configuration models with heavy tailed in-degrees

  • Cai, Xing Shi
  • Caputo, Pietro
  • Perarnau Llobet, Guillem
  • Quattropani, Matteo
We consider the extremal values of the stationary distribution of sparse directed random graphs with given degree sequences and their relation to the extremal values of the in-degree sequence. The graphs are generated by the directed configuration model. Under the assumption of bounded ( 2 + ¿ ) -moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have a power-law behavior, we show that the extremal values of the stationary distribution also have a power-law behavior with the same index. In the same setting, we prove that these results extend to the PageRank scores of the random digraph, thus confirming a version of the so-called power-law hypothesis. Along the way we establish several facts about the model, including the mixing time cutoff and the characterization of the typical values of the stationary distribution, which were previously obtained under the assumption of bounded in-degrees., The third author was supported by the Spanish Agencia Estatal de Investigación under projects MTM2017-82166-P and PID2020-113082GB-I00 and by the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M)., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Percolation on dense random graphs with given degrees

  • Lichev, Lyuben
  • Mitsche, Dieter
  • Perarnau Llobet, Guillem
In this paper, we study the order of the largest connected component of a random graph having two sources of randomness: first, the graph is chosen randomly from all graphs with a given degree sequence, and then bond percolation is applied. Far from being able to classify all such degree sequences, we exhibit several new threshold phenomena for the order of the largest component in terms of both sources of randomness. We also provide an example of a degree sequence for which the order of the largest component undergoes an unbounded number of jumps in terms of the percolation parameter, giving rise to a behavior that cannot be observed without percolation., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Approximation and decomposition in lattices of clutters

  • Martí Farré, Jaume
  • Mier Vinué, Anna de
A clutter on O is a family of subsets of O that are incomparable under inclusion. Given a collection S of clutters on O and another clutter ¿ on O, we study the problem of approximating and decomposing ¿ in terms of the clutters in S. We want to guarantee when these approximations exist not only for a single element ¿, but for all ¿ that belong to a family of clutters . We use the lattice structure of the collection of clutters to show that the existence of such approximations and decompositions for every clutter ¿ is equivalent to the fact that S contains a given family of irreducible elements determined by S and . We explicitly compute these irreducible families in some cases and apply our results to clutters arising from discrete objects such as matroids, graphs and secret sharing schemes., This work was partially supported by the Ministerio de Ciencia e Innovación/Agencia Estatal de Investigación, Spain, and the European Regional Development Fund under projects PGC2018-095471-B-I00 and PID2020-113082GB-I00; by AGAUR, Generalitat de Catalunya, from the Catalan Government under projects SGR-Cat 2021 00595 and SGR-Cat 2021 00585; by Universitat Politècnica de Catalunya under funds AGRUPUPC., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Grassl–Rötteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes

  • Ball, Simeon Michael
We prove that the cyclic and constacyclic codes constructed by Grassl and Rötteler in International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015) are generalised Reed–Solomon codes. This note can be considered as an addendum to Grassl and Rötteler International Symposium on Information Theory (ISIT), pp 1104–1108 (2015). It can also be considered as an appendix to Ball and Vilar IEEE Trans Inform Theory 68:3796–3805, (2022) where Conjecture 11 of International Symposium on Information Theory (ISIT), pp 1104–1108 (2015), which was stated for Grassl–Rötteler codes, is proven for generalised Reed–Solomon codes. The content of this note, together with IEEE Trans Inform Theory 68:3796–3805, (2022) therefore implies that Conjecture 11 from International Symposium on Information Theory (ISIT), pp. 1104–1108 (2015) is true., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Determining when a truncated generalised Reed-Solomon code is Hermitian self-orthogonal

  • Ball, Simeon Michael
  • Vilar Algueró, Ricard
© 20xx IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works, We prove that there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n¿q2 over Fq2 if and only if there is a polynomial g¿Fq2 of degree at most (q-k)q-1 such that g+gq has q2-n distinct zeros. This allows us to determine the smallest n for which there is a Hermitian self-orthogonal k -dimensional truncated generalised Reed-Solomon code of length n over Fq2 , verifying a conjecture of Grassl and Rötteler. We also provide examples of Hermitian self-orthogonal k -dimensional generalised Reed-Solomon codes of length q2+1 over Fq2 , for k=q-1 and q an odd power of two., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Normal limiting distributions for systems of linear equations in random sets

  • Rué Perna, Juan José
  • Wotzel, Maximilian
We consider the binomial random set model where each element in is chosen independently with probability . We show that for essentially all regimes of p and very general conditions for a matrix A and a column vector b, the count of specific integer solutions to the system of linear equations with the entries of x in follows a (conveniently rescaled) normal limiting distribution. This applies among others to the number of solutions with every variable having a different value, as well as to a broader class of so-called non-trivial solutions in homogeneous strictly balanced systems. Our proof relies on the delicate linear algebraic study both of the subjacent matrices and the corresponding ranks of certain submatrices, together with the application of the method of moments in probability theory., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Enumeration of chordal planar graphs and maps

  • Castellví Foguet, Jordi
  • Noy Serrano, Marcos
  • Requile, Clement
We determine the number of labelled chordal planar graphs with n vertices, which is asymptotically for a constant and . We also determine the number of rooted simple chordal planar maps with n edges, which is asymptotically , where , , and s is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from by repeatedly adding vertices adjacent to an existing triangular face., We gratefully acknowledge earlier discussions on this project with Erkan Narmanli. M.N. was supported by grants MTM2017-82166-P and PID2020-113082GB-I00, the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). C.R. was supported by the grant Beatriu de Pinós BP2019, funded by the H2020 COFUND project No 801370 and AGAUR (the Catalan agency for management of university and research grants), and the grant PID2020-113082GB-I00 of the Spanish Ministry of Science and Innovation., Peer Reviewed, Postprint (author's final draft)