Finding large structures in graphs and hypergraphs
ABSTRACT
One of the central topics in extremal combinatorics is determining sufficient conditions that guarantee a graph or hypergraph $G$ contains a specific, large substructure. To illustrate this, consider the problem of finding a cycle that visits every vertex (a Hamiltonian cycle). A classical theorem by Dirac provides a structural condition: if every vertex in an $n$-vertex graph $G$ is connected to at least half of the other vertices, a Hamiltonian cycle is guaranteed to exist. Alternatively, a notable probabilistic result by Pósa shows that if edges are formed randomly with probability $C \log n / n$, the graph will almost certainly contain such a cycle. This talk will provide an accessible overview of how these different perspectives—deterministic minimum degree conditions, pure randomness and pseudorandomness, and random perturbations—are used to find large structures, concluding with a look at recent developments in the field.
