Connections Workshop: Extremal Combinatorics: Spanning trees in pseudorandom graphs via sorting networks
Presenter
February 6, 2025
Keywords:
- extremal combinatorics
- extremal set theory
- extremal graph theory
- hypergraphs
- designs
- Ramsey theory
- positional games
- random graphs
- thresholds
- probabilistic combinatorics
- combinatorial probability
- statistical physics
- percolation
- structural graph theory
- graph minors
- chromatic number
- arithmetic combinatorics
- arithmetic progressions
- discrete geometry
- combinatorial geometry
- incidence theorems
MSC:
- 05B05 - Combinatorial aspects of block designs [See also 51E05
- 62K10]
- 05B07 - Triple systems
- 05C15 - Coloring of graphs and hypergraphs
- 05C20 - Directed graphs (digraphs)
- tournaments
- 05C22 - Signed and weighted graphs
- 05C25 - Graphs and abstract algebra (groups
- rings
- fields
- etc.) [See also 20F65]
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C50 - Graphs and linear algebra (matrices
- eigenvalues
- etc.)
- 05C51 - Graph designs and isomorphic decomposition [See also 05B30]
- 05C55 - Generalized Ramsey theory [See also 05D10]
- 05C57 - Games on graphs (graph-theoretic aspects) [See also 91A43
- 91A46]
- 05C65 - Hypergraphs
- 05C78 - Graph labelling (graceful graphs
- bandwidth
- 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
- 05C83 - Graph minors
- 05D05 - Extremal set theory
- 05D40 - Probabilistic methods in extremal combinatorics
- including polynomial methods (combinatorial Nullstellensatz
- 11B13 - Additive bases
- including sumsets [See also 05B10]
- 11B25 - Arithmetic progressions [See also 11N13]
- 11B30 - Arithmetic combinatorics
- higher degree uniformity
- 11P70 - Inverse problems of additive number theory
- including sumsets
- 52C10 - Erdős problems and related topics of discrete geometry [See also 11Hxx]
- 52C30 - Planar arrangements of lines and pseudolines (aspects of discrete geometry)
- 52C35 - Arrangements of points
- flats
- hyperplanes (aspects of discrete geometry) [See also 14N20
- 32S22]
- 60C05 - Combinatorial probability
Abstract
We show that \((n,d,\lambda)\)-graphs with \(\lambda=O(d/log^3n)\) are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. The key new idea in our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Koml\'{o}s and Szemer\'{e}di, with further applications to the vertex disjoint paths problem. Joint work with Joseph Hyde, Alp M\"{u}yesser, and Matías Pavez-Signé.