Introductory Workshop - Graph Theory: Extremal, Probabilistic and Structural: Probabilistic combinatorics and random graphs
Presenter
February 11, 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
I will give an introduction to probabilistic combinatorics and graph theory. The star of the story will be the Erdos-Renyi random graph, a graph on n vertices in which every edge is included with probability p. I will explain some of the reasons why this model has attracted so much attention in combinatorics in the last 60 years and describe its connections to computer science and physics.