Skip to main content

ESTRUCTURAS DISCRETAS, GEOMETRICAS Y ALEATORIAS

MTM2014-54745-P

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
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 2014
State Plan 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Management unit Secretaría de Estado de Educación, Formación Profesional y Universidades
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

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

A finite version of the Kakeya problem

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • Blokhuis, Aart
  • Domenzain, Diego
Let L be a set of lines of an affine space over a field and let S be a set of points with the property that every line of L is incident with at least N points of S. Let D be the set of directions of the lines of L considered as points of the projective space at infinity. We give a geometric construction of a set of lines L, where D contains an Nn−1 grid and where S has size 2( 1 2N) n plus smaller order terms, given a starting configuration in the plane. We provide examples of such starting configurations for the reals and for finite fields. Following Dvir’s proof of the finite field Kakeya conjecture and the idea of using multiplicities of Dvir, Kopparty, Saraf and Sudan, we prove a lower bound on the size of S dependent on the ideal generated by the homogeneous polynomials vanishing on D. This bound is maximised as ( 1 2N) n plus smaller order terms, for n > 4, when D contains the points of a Nn−1 grid.
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On zero-one and convergence laws for graphs embeddable on a fixed surface

  • Atserias, Albert|||0000-0002-3732-1989
  • Kreutzer, Stephan
  • Noy Serrano, Marcos|||0000-0002-2399-1359
We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law - and not even a convergence law - on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Random planar maps and graphs with minimum degree two and three

  • Noy Serrano, Marcos|||0000-0002-2399-1359
  • Ramos, Lander
We find precise asymptotic estimates for the number of planar maps and graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the core of a random planar graph is of order c log(n) for an explicit constant c. These results provide new information on the structure of random planar graphs., 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)

On the optimality of the uniform random strategy

  • kush, Christopher
  • Rué Perna, Juan José|||0000-0002-6420-3179
  • Spiegel, Christoph
  • Szabó, T.
Biased Maker-Breaker games, introduced by Chvátal and Erdos, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container-type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H-building games studied by Bednarska and Luczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game-theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging.
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

On sets defining few ordinary planes

  • Ball, Simeon Michael|||0000-0003-4845-2084
Let S be a set of n points in real three-dimensional space, no three collinear and not all co-planar. We prove that if the number of planes incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in the intersection of two quadrics. Furthermore, we prove that there is a constant c such that if the number of planes incident with exactly three points of S is less than (Formula presented.) then, for n sufficiently large, S is either a regular prism, a regular anti-prism, a regular prism with a point removed or a regular anti-prism with a point removed. As a corollary to the main result, we deduce the following theorem. Let S be a set of n points in the real plane. If the number of circles incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in a curve of degree at most four.
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)

On doubling and volume: chains

  • Freiman, Gregory A.
  • Serra Albó, Oriol|||0000-0001-8561-4631
The well-known Freiman–Ruzsa theorem provides a structural description of a set A of integers with |2A|=c|A| as a subset of a d–dimensional arithmetic progression P with |P|=c'|A|, where d and c' depend only on c. The estimation of the constants d and c' involved in the statement has been the object of intense research. Freiman conjectured in 2008 a formula for the largest volume of such a set. In this paper we prove the conjecture for a general class of sets called chains., Peer Reviewed
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)

On subsets of the normal rational curve

  • Ball, Simeon Michael|||0000-0003-4845-2084
  • De Beule, Jan
A normal rational curve of the (k-1) -dimensional projective space over Fq is an arc of size q+1 , since any k points of the curve span the whole space. In this paper, we will prove that if q is odd, then a subset of size 3k-6 of a normal rational curve cannot be extended to an arc of size q+2 . In fact, we prove something slightly stronger. Suppose that q is odd and E is a (2k-3) -subset of an arc G of size 3k-6 . If G projects to a subset of a conic from every (k-3) -subset of E , then G cannot be extended to an arc of size q+2 . Stated in terms of error-correcting codes we prove that a k -dimensional linear maximum distance separable code of length 3k-6 over a field Fq of odd characteristic, which can be extended to a Reed–Solomon code of length q+1 , cannot be extended to a linear maximum distance separable code of length q+2 .
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A Note on sparse supersaturation and extremal results for linear homogeneous systems

  • Spiegel, Christoph
We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Sz\'emeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, R\
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On zero-one and convergence laws for graphs embeddable on a fixed surface

  • Atserias, Albert
  • Kreutzer, Stephan
  • Noy Serrano, Marcos
We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law - and not even a convergence law - on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On the optimality of the uniform random strategy

  • kush, Christopher
  • Rué Perna, Juan José
  • Spiegel, Christoph
  • Szabó, T.
Biased Maker-Breaker games, introduced by Chvátal and Erdos, are central to the field of positional games and have deep connections to the theory of random structures. The main questions are to determine the smallest bias needed by Breaker to ensure that Maker ends up with an independent set in a given hypergraph. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies certain “container-type” regularity conditions. This will enable us to answer the main question for hypergraph generalizations of the H-building games studied by Bednarska and Luczak as well as a generalization of the van der Waerden games introduced by Beck. We find it remarkable that a purely game-theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, while the analogous questions about sparse random discrete structures are usually quite challenging., 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)

A finite version of the Kakeya problem

  • Ball, Simeon Michael
  • Blokhuis, Aart
  • Domenzain, Diego
Let L be a set of lines of an affine space over a field and let S be a set of points with the property that every line of L is incident with at least N points of S. Let D be the set of directions of the lines of L considered as points of the projective space at infinity. We give a geometric construction of a set of lines L, where D contains an Nn−1 grid and where S has size 2( 1 2N) n plus smaller order terms, given a starting configuration in the plane. We provide examples of such starting configurations for the reals and for finite fields. Following Dvir’s proof of the finite field Kakeya conjecture and the idea of using multiplicities of Dvir, Kopparty, Saraf and Sudan, we prove a lower bound on the size of S dependent on the ideal generated by the homogeneous polynomials vanishing on D. This bound is maximised as ( 1 2N) n plus smaller order terms, for n > 4, when D contains the points of a Nn−1 grid., Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A Note on sparse supersaturation and extremal results for linear homogeneous systems

  • Spiegel, Christoph
We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Sz\'emeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, R\, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On sets defining few ordinary planes

  • Ball, Simeon Michael
Let S be a set of n points in real three-dimensional space, no three collinear and not all co-planar. We prove that if the number of planes incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in the intersection of two quadrics. Furthermore, we prove that there is a constant c such that if the number of planes incident with exactly three points of S is less than (Formula presented.) then, for n sufficiently large, S is either a regular prism, a regular anti-prism, a regular prism with a point removed or a regular anti-prism with a point removed. As a corollary to the main result, we deduce the following theorem. Let S be a set of n points in the real plane. If the number of circles incident with exactly three points of S is less than (Formula presented.) for some (Formula presented.) then, for n sufficiently large, all but at most O(K) points of S are contained in a curve of degree at most four., Postprint (updated version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On doubling and volume: chains

  • Freiman, Gregory A.
  • Serra Albó, Oriol
The well-known Freiman–Ruzsa theorem provides a structural description of a set A of integers with |2A|=c|A| as a subset of a d–dimensional arithmetic progression P with |P|=c'|A|, where d and c' depend only on c. The estimation of the constants d and c' involved in the statement has been the object of intense research. Freiman conjectured in 2008 a formula for the largest volume of such a set. In this paper we prove the conjecture for a general class of sets called chains., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

On subsets of the normal rational curve

  • Ball, Simeon Michael
  • De Beule, Jan
A normal rational curve of the (k-1) -dimensional projective space over Fq is an arc of size q+1 , since any k points of the curve span the whole space. In this paper, we will prove that if q is odd, then a subset of size 3k-6 of a normal rational curve cannot be extended to an arc of size q+2 . In fact, we prove something slightly stronger. Suppose that q is odd and E is a (2k-3) -subset of an arc G of size 3k-6 . If G projects to a subset of a conic from every (k-3) -subset of E , then G cannot be extended to an arc of size q+2 . Stated in terms of error-correcting codes we prove that a k -dimensional linear maximum distance separable code of length 3k-6 over a field Fq of odd characteristic, which can be extended to a Reed–Solomon code of length q+1 , cannot be extended to a linear maximum distance separable code of length q+2 ., Postprint (updated version)
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)

Random planar maps and graphs with minimum degree two and three

  • Noy Serrano, Marcos
  • Ramos, Lander
We find precise asymptotic estimates for the number of planar maps and graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the core of a random planar graph is of order c log(n) for an explicit constant c. These results provide new information on the structure of random planar graphs., Peer Reviewed, Postprint (published version)
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)