Introductory Workshop - Graph Theory: Extremal, Probabilistic and Structural: On Hypercube Statistics
Presenter
February 10, 2025
Keywords:
- extremal graph theory
- random graphs
- probabilistic methods
- structural graph theory
- Ramsey theory
MSC:
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C55 - Generalized Ramsey theory [See also 05D10]
- 05C75 - Structural characterization of families of graphs
- 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
- 05D40 - Probabilistic methods in extremal combinatorics
- including polynomial methods (combinatorial Nullstellensatz
- etc.)
Abstract
For a subset A of vertices of the n-dimensional cube Q_n, let lambda(n,d,s,A) denote the fraction of d-dimensional subcubes of Q_n that contain exactly s points of A. Let lambda(n,d,s) denote the maximum possible value of lambda(n,d,s,A), as A ranges over all subsets of vertices of Q_n, and let lambda(d,s) denote the limit of this quantity as n tends to infinity. I will discuss the problem of determining or estimating the quantities lambda(d,s), describing several intriguing conjectures and some (modest) results. Joint work with Maria Axenovich and John Goldwasser.