Algebraic and Analytic Methods in Combinatorics: Independence in random graphs
Presenter
March 20, 2025
Keywords:
- extremal combinatorics
- extremal graph theory
- probabilistic combinatorics
- discrete geometry
- additive combinatorics
- combinatorial geometry
- incidence geometry
- arithmetic progressions
- Discrete analysis
MSC:
- 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.)
- 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
- 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
Various random graphs models satisfy that each edge appears independently of all other edges but those in a bounded degree graph. Examples include Erdős–Rényi random graphs, random Cayley graphs, random Latin square graphs, and random entangled graphs. We begin the systematic study of random graphs under this weak independence hypothesis, focusing on the clique number. We prove that for 0