Extremal Graph Theory

Question 1

What is Mantel’s Theorem?

Answer 1

Every n-vertex triangle free graph has at mose n^2/4 edges

Question 2

What is Turan’s Theorem?

Answer 2

Every n-vertex K_{k+1}-free graph has at most ((k-1)/2k)n^2 edges

Question 3

What is Zykov’s Theorem? Aka a generalisation of Turan’s Theorem.

Answer 3

For k \leq l \leq 0, every n-vertex K_{k+1}-free graph has at most (k choose l)(n/k)^l copies of K_l

Question 4

What is the Erdos-Stone Theorem?

Answer 4

Every non-bipartite graph H with chromatic number \chi(H) = k+1, the maximum number of edges in an n-vertex H-free graph is (1+o(1))((k-1)/2k)n^2, where o(1) denotes a term tending to 0 as n–>infinity.

Question 5

What is the maximum number of edges in an n-vertex C_4-free graph?

Answer 5

((1/2)+o(1))n^(3/2), where o(1) denotes a term tending to 0 as n–>infinity.

Question 6

What is Kovari, Sos and Turan’s Theorem about excluding complete bipartite graphs?

Answer 6

For s \leq t \leq 1 there is an integer c such that the number of edges in an n-vertex graph G with no K_{s,t} subgraph is at most cn^(2-(1/t))