Skip to main content

COMBINATORIA GEOMETRICA, ALGEBRAICA Y PROBABILISTICA

MTM2017-82166-P

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprogram Subprograma Estatal de Generación de Conocimiento
Call Proyectos de I+D (Excelencia / Generación de Conocimiento)
Call year 2017
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Artículo científico (JournalArticle)

On varieties defined by large sets of quadrics and their application to error-correcting codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Pepe, Valentina
Let U be a ( k-1 2 - 1)-dimensional subspace of quadratic forms defined on F k with the property that U does not contain any reducible quadratic form. Let V (U) be the points of PG(k - 1, F) which are zeros of all quadratic forms in U. We will prove that if there is a group G which fixes U and no line of PG(k - 1, F) and V (U) spans PG(k - 1, F) then any hyperplane of PG(k - 1, F) is incident with at most k points of V (U). If F is a finite field then the linear code generated by the matrix whose columns are the points of V (U) is a k-dimensional linear code of length |V (U)| and minimum distance at least |V (U)| - k. A linear code with these parameters is an MDS code or an almost MDS code. We will construct examples of such subspaces U and groups G, which include the normal rational curve, the elliptic curve, Glynn’s arc from [8] and other examples found by computer search. We conjecture that the projection of V (U) from any k - 4 points is contained in the intersection of two quadrics, the common zeros of two linearly independent quadratic forms. This would be a strengthening of a classical theorem of Fano, which itself is an extension of a theorem of Castelnuovo, for which we include a proof using only linear algebra.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Arcs in finite projective spaces

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Lavrauw, Michel
This is an expository article detailing results concerning large arcs in finite projective spaces. It is not strictly a survey but attempts to cover the most relevant results on arcs, simplifying and unifying proofs of known old and more recent theorems. The article is mostly self-contained and includes a proof of the most general form of Segre’s lemma of tangents and a short proof of the MDS conjecture over prime fields based on this lemma.
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Set systems with distinct sumsets

  • Cilleruelo, Javier
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Wötzel, Maximilian|||0000-0001-7591-0998
A family $\mathcal{A}$ of $k$-subsets of $\{1,2,\dots, N\}$ is a Sidon system if the sumsets $A+A'$, $A,A'\in \mathcal{A}$ are pairwise distinct. We show that the largest cardinality $F_k(N)$ of a Sidon system of $k$-subsets of $[N]$ satisfies $F_k(N)\le {N-1\choose k-1}+N-k$ and the asymptotic lower bound $F_k(N)=\Omega_k(N^{k-1})$. More precise bounds on $F_k(N)$ are obtained for $k\le 3$. We also obtain the threshold probability for a random system to be Sidon for $k= 2$ and $3$., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

Graph polynomials and group coloring of graphs

  • Bosek, Bartlomiej
  • Grytczuk, Jaroslaw
  • Gutowski, Grzegorz
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Zajac, Mariusz
Let A be an Abelian group and let G be a simple graph. We say that G is A-colorable if, for some fixed orientation of G and every edge labeling l:E(G)¿A, there exists a vertex coloring c by the elements of A such that c(y)-c(x)¿l(e), for every edge e=xy (oriented from x to y). Given an arbitrary field F, suppose that each edge e=xy of G is assigned a triple (ae,be,ce)¿F3, with ae,be¿0. We say that G is F-colorable if for every such edge labeling there exists a vertex coloring f by the elements of F such that aef(x)+bef(y)+ce¿0, for every edge e=xy. Clearly, F-colorability of a graph implies its A-colorability, where A is the additive group of the field F. A graph G is said to be F-k-choosable if it is F-colorable from arbitrary lists of elements of F, each of size k, assigned to the vertices. Recently, R. Langhede and C. Thomassen [Discrete Math. 344 (2021), no. 9, Paper No. 112474; MR4268692] proved that every simple planar graph on n vertices is Z5-colorable and moreover it has at least 2n/9 different Z5-colorings. In the paper under review, using a different approach based on graph polynomials, the authors extend this result to K5-minor-free graphs in the more general setting of field coloring. More specifically, they prove that every such graph on n vertices is F-5-choosable, whenever F is an arbitrary field with at least 5 elements. Moreover, the number of colorings (for every list assignment) is at least 5n/4., Supported by the Polish National Science Center, Grant Number: NCN 2019/35/B/ST6/02472. Oriol Serra acknowledges financial support from the Spanish Agencia Estatal de Investigación under project MTM2017-82166-P., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Artículo científico (JournalArticle)

On sets defining few ordinary solids

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Jiménez Izquierdo, Enrique
The version of record is available online at: http://dx.doi.org/10.1007/s00454-021-00302-7, Let S be a set of n points in real four-dimensional space, no four coplanar and spanning the whole space. We prove that if the number of solids incident with exactly four points of S is less than Kn3 for some K=o(n1/7) then, for n sufficiently large, all but at most O(K) points of S are contained in the intersection of five linearly independent quadrics. Conversely, we prove that there are finite subgroups of size n of an elliptic curve that span less than n3/6 solids containing exactly four points of S., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial

  • Aliste Prieto, José
  • Mier Vinué, Anna de|||0000-0002-2817-7807
  • Zamora Ponce, José
© 2021. Elsevier, In this article, we construct explicit examples of pairs of non-isomorphic trees with the same restricted U -polynomial for every k; by this we mean that the polynomials agree on terms with degree at most k + 1. The main tool for this construction is a generalization of the U -polynomial to rooted graphs, which we introduce and study in this article. Most notably we show that rooted trees can be reconstructed from its rooted U -polynomial., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The geometry of Hermitian self-orthogonal codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Vilar Algueró, Ricard
The version of record of this article, first published in Journal of geometry, is available online at Publisher’s website: http://dx.doi.org/10.1007/s00022-021-00619-x, We prove that if n>k2 then a k-dimensional linear code of length n over Fq2 has a truncation which is linearly equivalent to a Hermitian self-orthogonal linear code. In the contrary case we prove that truncations of linear codes to codes equivalent to Hermitian self-orthogonal linear codes occur when the columns of a generator matrix of the code do not impose independent conditions on the space of Hermitian forms. In the case that there are more than n common zeros to the set of Hermitian forms which are zero on the columns of a generator matrix of the code, the additional zeros give the extension of the code to a code that has a truncation which is equivalent to a Hermitian self-orthogonal code., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The equivalence of linear codes implies semi-linear equivalence

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

Additive volume of sets contained in few arithmetic progressions

  • Freiman, Gregory A.
  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Spiegel, Christoph
A conjecture of Freiman gives an exact formula for the largest volume of a finite set A of integers with given cardinality k=|A| and doubling T=|2A|. The formula is known to hold when T=3k-4, for some small range over 3k-4 and for families of structured sets called chains. In this paper we extend the formula to sets of every dimension and prove it for sets composed of three segments, giving structural results for the extremal case. A weaker extension to sets composed of a bounded number of segments is also discussed., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Arcs and tensors

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Lavrauw, Michel
This is a post-peer-review, pre-copyedit version of an article published in Designs, Codes, and Cryptography. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10623-019-00668-z, To an arc A of PG(k-1,q) of size q+k-1-t we associate a tensor in ¿¿k,t(A)¿¿k-1 , where ¿k,t denotes the Veronese map of degree t defined on PG(k-1,q) . As a corollary we prove that for each arc A in PG(k-1,q) of size q+k-1-t , which is not contained in a hypersurface of degree t, there exists a polynomial F(Y1,…,Yk-1) (in k(k-1) variables) where Yj=(Xj1,…,Xjk) , which is homogeneous of degree t in each of the k-tuples of variables Yj , which upon evaluation at any (k-2) -subset S of the arc A gives a form of degree t on PG(k-1,q) whose zero locus is the tangent hypersurface of A at S, i.e. the union of the tangent hyperplanes of A at S. This generalises the equivalent result for planar arcs ( k=3 ), proven in [2], to arcs in projective spaces of arbitrary dimension. A slightly weaker result is obtained for arcs in PG(k-1,q) of size q+k-1-t which are contained in a hypersurface of degree t. We also include a new proof of the Segre–Blokhuis–Bruen–Thas hypersurface associated to an arc of hyperplanes in PG(k-1,q) .
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Weak components of the directed configuration model

  • Coulson, Matthew John
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
The version of record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_109, We study the threshold for the existence of a linear order weakly connected component in the directed configuration model, confirming analytic but non-rigorous results recently obtained by Kryven [8]. We also establish convergence in probability of the fraction of vertices and edges that are contained in the largest component. As a consequence of our results, we obtain that the “separation” between the thresholds for the existence a giant weakly and strongly connected component is in some sense independent from the in-/out-degree correlation. We formalise this idea using bond percolation., G. Perarnau—Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017-82166-P and the MSCA-RISE-2020-101007705 - ‘RandNet’., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Universal singular exponents in catalytic variable equations

  • Drmota, Michael
  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Yu, Guan-Ru
Catalytic equations appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that the asymptotic estimate for the coefficients of the solutions of (so-called) positive catalytic equations has a universal asymptotic behavior. In particular, this provides a rationale why the number of maps of size n in various planar map classes grows asymptotically like , for suitable positive constants c and ¿. Essentially we have to distinguish between linear catalytic equations (where the subexponential growth is ) and non-linear catalytic equations (where we have as in planar maps). Furthermore we provide a quite general central limit theorem for parameters that can be encoded by catalytic functional equations, even when they are not positive., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

Some constructions of quantum MDS codes

  • Ball, Simeon Michael|||0000-0003-4845-2084
​The version of record os available online at: http://dx.doi.org/10.1007/s10623-021-00846-y, We construct quantum MDS codes with parameters [[q2+1,q2+3-2d,d]]q for all d¿q+1, d¿q. These codes are shown to exist by proving that there are classical generalised Reed–Solomon codes which contain their Hermitian dual. These constructions include many constructions which were previously known but in some cases these codes are new. We go on to prove that if d¿q+2 then there is no generalised Reed–Solomon [n,n-d+1,d]q2 code which contains its Hermitian dual. We also construct an [[18,0,10]]5 quantum MDS code, an [[18,0,10]]7 quantum MDS code and a [[14,0,8]]5 quantum MDS code, which are the first quantum MDS codes discovered for which d¿q+3, apart from the [[10,0,6]]3 quantum MDS code derived from Glynn’s code.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

  • Drmota, Michael
  • Ramos Garrido, Lander
  • Requilé, Clément
  • Rué Perna, Juan José|||0000-0002-6420-3179
The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and seriesparallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988].
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

On list k-coloring convex bipartite 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
List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

The giant component of the directed configuration model revisited

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
We prove a law of large numbers for the order and size of the largest strongly connected component in the directed configuration model. Our result extends previous work by Cooper and Frieze (2004)., Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017- 82166-P and the MSCA-RISE-2020-101007705 - ’RandNet’. 1517
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On the expected number of perfect matchings in cubic planar graphs

  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Requile, Clement|||0000-0002-7689-7972
A well-known conjecture by Lovász and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically c¿n , where c > 0 and ¿ ~ 1.14196 is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Artículo científico (JournalArticle)

Frozen (¿ + 1)-colourings of bounded degree graphs

  • Bonamy, Marthe
  • Bousquet, Nicolas
  • Perarnau Llobet, Guillem|||0000-0002-1953-9511
Let G be a graph on n vertices and with maximum degree ¿, and let k be an integer. The k-recolouring graph of G is the graph whose vertices are k-colourings of G and where two k-colourings are adjacent if they differ at exactly one vertex. It is well known that the k-recolouring graph is connected for . Feghali, Johnson and Paulusma (J. Graph Theory 83 (2016) 340–358) showed that the (¿ + 1)-recolouring graph is composed by a unique connected component of size at least 2 and (possibly many) isolated vertices. In this paper, we study the proportion of isolated vertices (also called frozen colourings) in the (¿ + 1)-recolouring graph. Our first contribution is to show that if G is connected, the proportion of frozen colourings of G is exponentially smaller in n than the total number of colourings. This motivates the use of the Glauber dynamics to approximate the number of (¿ + 1)-colourings of a graph. In contrast to the conjectured mixing time of O(nlog n) for colours, we show that the mixing time of the Glauber dynamics for (¿ + 1)-colourings restricted to non-frozen colourings can be O(n 2). Finally, we prove some results about the existence of graphs with large girth and frozen colourings, and study frozen colourings in random regular graphs.
UPCommons. Portal del coneixement obert de la UPC
Publication 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
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Extremal families for Kruskal-Katona Theorem

  • Serra Albó, Oriol|||0000-0001-8561-4631
  • Vena Cros, Lluís|||0000-0002-0075-3673
Given a set of size $n$ and a positive integer $k<n$, Kruskal--Katona theorem gives the minimum size of the shadow of a family $S$ of $k$-sets of $[n]$ in terms of the cardinality of $S$. We give a characterization of the families of $k$-sets satisfying equality in Kruskal--Katona theorem. This answers a question of F\"uredi and Griggs., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Weak components of the directed configuration model

  • Coulson, Matthew John
  • Perarnau Llobet, Guillem
The version of record is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_109, We study the threshold for the existence of a linear order weakly connected component in the directed configuration model, confirming analytic but non-rigorous results recently obtained by Kryven [8]. We also establish convergence in probability of the fraction of vertices and edges that are contained in the largest component. As a consequence of our results, we obtain that the “separation” between the thresholds for the existence a giant weakly and strongly connected component is in some sense independent from the in-/out-degree correlation. We formalise this idea using bond percolation., G. Perarnau—Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017-82166-P and the MSCA-RISE-2020-101007705 - ‘RandNet’., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Additive volume of sets contained in few arithmetic progressions

  • Freiman, Gregory A.
  • Serra Albó, Oriol
  • Spiegel, Christoph
A conjecture of Freiman gives an exact formula for the largest volume of a finite set A of integers with given cardinality k=|A| and doubling T=|2A|. The formula is known to hold when T=3k-4, for some small range over 3k-4 and for families of structured sets called chains. In this paper we extend the formula to sets of every dimension and prove it for sets composed of three segments, giving structural results for the extremal case. A weaker extension to sets composed of a bounded number of segments is also discussed., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Arcs and tensors

  • Ball, Simeon Michael
  • Lavrauw, Michel
This is a post-peer-review, pre-copyedit version of an article published in Designs, Codes, and Cryptography. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10623-019-00668-z, To an arc A of PG(k-1,q) of size q+k-1-t we associate a tensor in ¿¿k,t(A)¿¿k-1 , where ¿k,t denotes the Veronese map of degree t defined on PG(k-1,q) . As a corollary we prove that for each arc A in PG(k-1,q) of size q+k-1-t , which is not contained in a hypersurface of degree t, there exists a polynomial F(Y1,…,Yk-1) (in k(k-1) variables) where Yj=(Xj1,…,Xjk) , which is homogeneous of degree t in each of the k-tuples of variables Yj , which upon evaluation at any (k-2) -subset S of the arc A gives a form of degree t on PG(k-1,q) whose zero locus is the tangent hypersurface of A at S, i.e. the union of the tangent hyperplanes of A at S. This generalises the equivalent result for planar arcs ( k=3 ), proven in [2], to arcs in projective spaces of arbitrary dimension. A slightly weaker result is obtained for arcs in PG(k-1,q) of size q+k-1-t which are contained in a hypersurface of degree t. We also include a new proof of the Segre–Blokhuis–Bruen–Thas hypersurface associated to an arc of hyperplanes in PG(k-1,q) ., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

On the expected number of perfect matchings in cubic planar graphs

  • Noy Serrano, Marcos
  • Rué Perna, Juan José
  • Requile, Clement
A well-known conjecture by Lovász and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically c¿n , where c > 0 and ¿ ~ 1.14196 is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On varieties defined by large sets of quadrics and their application to error-correcting codes

  • Ball, Simeon Michael
  • Pepe, Valentina
Let U be a ( k-1 2 - 1)-dimensional subspace of quadratic forms defined on F k with the property that U does not contain any reducible quadratic form. Let V (U) be the points of PG(k - 1, F) which are zeros of all quadratic forms in U. We will prove that if there is a group G which fixes U and no line of PG(k - 1, F) and V (U) spans PG(k - 1, F) then any hyperplane of PG(k - 1, F) is incident with at most k points of V (U). If F is a finite field then the linear code generated by the matrix whose columns are the points of V (U) is a k-dimensional linear code of length |V (U)| and minimum distance at least |V (U)| - k. A linear code with these parameters is an MDS code or an almost MDS code. We will construct examples of such subspaces U and groups G, which include the normal rational curve, the elliptic curve, Glynn’s arc from [8] and other examples found by computer search. We conjecture that the projection of V (U) from any k - 4 points is contained in the intersection of two quadrics, the common zeros of two linearly independent quadratic forms. This would be a strengthening of a classical theorem of Fano, which itself is an extension of a theorem of Castelnuovo, for which we include a proof using only linear algebra., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication Artículo científico (JournalArticle)

Graph polynomials and group coloring of graphs

  • Bosek, Bartlomiej
  • Grytczuk, Jaroslaw
  • Gutowski, Grzegorz
  • Serra Albó, Oriol
  • Zajac, Mariusz
Let A be an Abelian group and let G be a simple graph. We say that G is A-colorable if, for some fixed orientation of G and every edge labeling l:E(G)¿A, there exists a vertex coloring c by the elements of A such that c(y)-c(x)¿l(e), for every edge e=xy (oriented from x to y). Given an arbitrary field F, suppose that each edge e=xy of G is assigned a triple (ae,be,ce)¿F3, with ae,be¿0. We say that G is F-colorable if for every such edge labeling there exists a vertex coloring f by the elements of F such that aef(x)+bef(y)+ce¿0, for every edge e=xy. Clearly, F-colorability of a graph implies its A-colorability, where A is the additive group of the field F. A graph G is said to be F-k-choosable if it is F-colorable from arbitrary lists of elements of F, each of size k, assigned to the vertices. Recently, R. Langhede and C. Thomassen [Discrete Math. 344 (2021), no. 9, Paper No. 112474; MR4268692] proved that every simple planar graph on n vertices is Z5-colorable and moreover it has at least 2n/9 different Z5-colorings. In the paper under review, using a different approach based on graph polynomials, the authors extend this result to K5-minor-free graphs in the more general setting of field coloring. More specifically, they prove that every such graph on n vertices is F-5-choosable, whenever F is an arbitrary field with at least 5 elements. Moreover, the number of colorings (for every list assignment) is at least 5n/4., Supported by the Polish National Science Center, Grant Number: NCN 2019/35/B/ST6/02472. Oriol Serra acknowledges financial support from the Spanish Agencia Estatal de Investigación under project MTM2017-82166-P., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Universal singular exponents in catalytic variable equations

  • Drmota, Michael
  • Noy Serrano, Marcos
  • Yu, Guan-Ru
Catalytic equations appear in several combinatorial applications, most notably in the enumeration of lattice paths and in the enumeration of planar maps. The main purpose of this paper is to show that the asymptotic estimate for the coefficients of the solutions of (so-called) positive catalytic equations has a universal asymptotic behavior. In particular, this provides a rationale why the number of maps of size n in various planar map classes grows asymptotically like , for suitable positive constants c and ¿. Essentially we have to distinguish between linear catalytic equations (where the subexponential growth is ) and non-linear catalytic equations (where we have as in planar maps). Furthermore we provide a quite general central limit theorem for parameters that can be encoded by catalytic functional equations, even when they are not positive., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On the smallest trees with the same restricted U-polynomial and the rooted U-polynomial

  • Aliste Prieto, José
  • Mier Vinué, Anna de
  • Zamora Ponce, José
© 2021. Elsevier, In this article, we construct explicit examples of pairs of non-isomorphic trees with the same restricted U -polynomial for every k; by this we mean that the polynomials agree on terms with degree at most k + 1. The main tool for this construction is a generalization of the U -polynomial to rooted graphs, which we introduce and study in this article. Most notably we show that rooted trees can be reconstructed from its rooted U -polynomial., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Arcs in finite projective spaces

  • Ball, Simeon Michael
  • Lavrauw, Michel
This is an expository article detailing results concerning large arcs in finite projective spaces. It is not strictly a survey but attempts to cover the most relevant results on arcs, simplifying and unifying proofs of known old and more recent theorems. The article is mostly self-contained and includes a proof of the most general form of Segre’s lemma of tangents and a short proof of the MDS conjecture over prime fields based on this lemma., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

The giant component of the directed configuration model revisited

  • Cai, Xing Shi
  • Perarnau Llobet, Guillem
We prove a law of large numbers for the order and size of the largest strongly connected component in the directed configuration model. Our result extends previous work by Cooper and Frieze (2004)., Supported by the Spanish Ministerio de Economía y Competitividad project MTM2017- 82166-P and the MSCA-RISE-2020-101007705 - ’RandNet’. 1517, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Extremal families for Kruskal-Katona Theorem

  • Serra Albó, Oriol
  • Vena Cros, Lluís
Given a set of size $n$ and a positive integer $k<n$, Kruskal--Katona theorem gives the minimum size of the shadow of a family $S$ of $k$-sets of $[n]$ in terms of the cardinality of $S$. We give a characterization of the families of $k$-sets satisfying equality in Kruskal--Katona theorem. This answers a question of F\"uredi and Griggs., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

The geometry of Hermitian self-orthogonal codes

  • Ball, Simeon Michael
  • Vilar Algueró, Ricard
The version of record of this article, first published in Journal of geometry, is available online at Publisher’s website: http://dx.doi.org/10.1007/s00022-021-00619-x, We prove that if n>k2 then a k-dimensional linear code of length n over Fq2 has a truncation which is linearly equivalent to a Hermitian self-orthogonal linear code. In the contrary case we prove that truncations of linear codes to codes equivalent to Hermitian self-orthogonal linear codes occur when the columns of a generator matrix of the code do not impose independent conditions on the space of Hermitian forms. In the case that there are more than n common zeros to the set of Hermitian forms which are zero on the columns of a generator matrix of the code, the additional zeros give the extension of the code to a code that has a truncation which is equivalent to a Hermitian self-orthogonal code., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Frozen (¿ + 1)-colourings of bounded degree graphs

  • Bonamy, Marthe
  • Bousquet, Nicolas
  • Perarnau Llobet, Guillem
Let G be a graph on n vertices and with maximum degree ¿, and let k be an integer. The k-recolouring graph of G is the graph whose vertices are k-colourings of G and where two k-colourings are adjacent if they differ at exactly one vertex. It is well known that the k-recolouring graph is connected for . Feghali, Johnson and Paulusma (J. Graph Theory 83 (2016) 340–358) showed that the (¿ + 1)-recolouring graph is composed by a unique connected component of size at least 2 and (possibly many) isolated vertices. In this paper, we study the proportion of isolated vertices (also called frozen colourings) in the (¿ + 1)-recolouring graph. Our first contribution is to show that if G is connected, the proportion of frozen colourings of G is exponentially smaller in n than the total number of colourings. This motivates the use of the Glauber dynamics to approximate the number of (¿ + 1)-colourings of a graph. In contrast to the conjectured mixing time of O(nlog n) for colours, we show that the mixing time of the Glauber dynamics for (¿ + 1)-colourings restricted to non-frozen colourings can be O(n 2). Finally, we prove some results about the existence of graphs with large girth and frozen colourings, and study frozen colourings in random regular graphs., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On sets defining few ordinary solids

  • Ball, Simeon Michael
  • Jiménez Izquierdo, Enrique
The version of record is available online at: http://dx.doi.org/10.1007/s00454-021-00302-7, Let S be a set of n points in real four-dimensional space, no four coplanar and spanning the whole space. We prove that if the number of solids incident with exactly four points of S is less than Kn3 for some K=o(n1/7) then, for n sufficiently large, all but at most O(K) points of S are contained in the intersection of five linearly independent quadrics. Conversely, we prove that there are finite subgroups of size n of an elliptic curve that span less than n3/6 solids containing exactly four points of S., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Maximal independent sets and maximal matchings in series-parallel and related graph classes

  • Drmota, Michael
  • Ramos Garrido, Lander
  • Requilé, Clément
  • Rué Perna, Juan José
The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and seriesparallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Artículo científico (JournalArticle)

Some constructions of quantum MDS codes

  • Ball, Simeon Michael
​The version of record os available online at: http://dx.doi.org/10.1007/s10623-021-00846-y, We construct quantum MDS codes with parameters [[q2+1,q2+3-2d,d]]q for all d¿q+1, d¿q. These codes are shown to exist by proving that there are classical generalised Reed–Solomon codes which contain their Hermitian dual. These constructions include many constructions which were previously known but in some cases these codes are new. We go on to prove that if d¿q+2 then there is no generalised Reed–Solomon [n,n-d+1,d]q2 code which contains its Hermitian dual. We also construct an [[18,0,10]]5 quantum MDS code, an [[18,0,10]]7 quantum MDS code and a [[14,0,8]]5 quantum MDS code, which are the first quantum MDS codes discovered for which d¿q+3, apart from the [[10,0,6]]3 quantum MDS code derived from Glynn’s code., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Set systems with distinct sumsets

  • Cilleruelo, Javier
  • Serra Albó, Oriol
  • Wötzel, Maximilian
A family $\mathcal{A}$ of $k$-subsets of $\{1,2,\dots, N\}$ is a Sidon system if the sumsets $A+A'$, $A,A'\in \mathcal{A}$ are pairwise distinct. We show that the largest cardinality $F_k(N)$ of a Sidon system of $k$-subsets of $[N]$ satisfies $F_k(N)\le {N-1\choose k-1}+N-k$ and the asymptotic lower bound $F_k(N)=\Omega_k(N^{k-1})$. More precise bounds on $F_k(N)$ are obtained for $k\le 3$. We also obtain the threshold probability for a random system to be Sidon for $k= 2$ and $3$., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On list k-coloring convex bipartite graphs

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication 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)
Dipòsit Digital de Documents de la UAB
Publication Artículo científico (JournalArticle)

On the expected number of perfect matchings in cubic planar graphs

  • Noy, Marc
  • Requilé, Clément
  • Rué, Juanjo|||0000-0002-6420-3179
A well-known conjecture by Lov'asz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. ([13]). On the other hand, Chudnovsky and Seymour ([8]) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically cγn, where c.