Search
next up previous
Next: Penny Haxell - Integer Up: Extremal Combinatorics / Combinatoire Previous: David Fisher - The

Jerrold Griggs - Extremal graphs with bounded densities of small subgraphs



JERROLD GRIGGS, Department of Mathematics, University of South Carolina, Columbia, South Carolina  29208, USA
Extremal graphs with bounded densities of small subgraphs


Let $\textrm{Ex}(n,k,\mu)$ denote the maximum number of edges of an n-vertex graph in which every subgraph of k vertices has at most $\mu$ edges. Here we summarize some known results for the problem of determining $\textrm{Ex}(n,k,\mu)$, present simple new proofs, and provide new estimates and extremal graphs. One of our main aims is to show how the classical Turán theory can be applied to such problems. The case $\mu={k\choose
2}-1$ is the famous result of Turán. This is joint work with Miklós Simonovits and George Rubin Thomas.