Term Test 2 Review

Section 11.2 Term Test 2 Review

Term Test 2 covers Chapters 3, 4 and 5: classical extremal graph theory, Turán density, bipartite extremal numbers, supersaturation, homomorphism density, regular pairs, counting lemmas, the Regularity Lemma and triangle removal. Assignments 3 and 4 are the most relevant assignments for this test.

🔗

Subsection 11.2.1 Definitions to know

For a graph \(H\) and \(n\in\mathbb{N}\text{,}\) define the extremal number \(\ex(n,H)\text{.}\)
🔗

🔗
Define the Turán density \(\pi(H)\) of a graph \(H\text{.}\)
🔗

🔗
Define a graph homomorphism from \(H\) to \(G\text{.}\)
🔗

🔗
Define the homomorphism density \(t(H,G)\text{.}\)
🔗

🔗
Define the edge density \(d(A,B)\) between two disjoint vertex sets \(A\) and \(B\text{.}\)
🔗

🔗
Define what it means for a pair \((A,B)\) of disjoint vertex sets to be \(\varepsilon\)-regular.
🔗

🔗
Define the mean square density of a partition, as used in the proof of the Regularity Lemma.
🔗

🔗
Define an arithmetic progression.
🔗

🔗

🔗

Subsection 11.2.2 Theorem statements to know

State Mantel’s Theorem.
🔗

🔗
State Turán’s Theorem.
🔗

🔗
State the Erdős-Stone Theorem.
🔗

🔗
State the Kövári-Sós-Turán Theorem.
🔗

🔗
State the standard corollary of Kövári-Sós-Turán giving an upper bound on \(\ex(n,H)\) when \(H\) is bipartite.
🔗

🔗
State the special upper bound for \(\ex(n,C_4)\text{.}\)
🔗

🔗
State the weak Bondy-Simonovits even-cycle bound covered in lecture.
🔗

🔗
State Goodman’s Bound on the number of triangles in a graph with a given number of vertices and edges.
🔗

🔗
State Sidorenko’s inequality for \(C_4\text{:}\) the relationship between \(t(C_4,G)\) and \(t(K_2,G)\text{.}\)
🔗

🔗
State the even-cycle version of Sidorenko’s inequality: the relationship between \(t(C_{2k},G)\) and \(t(K_2,G)\text{.}\)
🔗

🔗
State the Erdős-Simonovits Supersaturation Theorem.
🔗

🔗
State the Counting Lemma for triangles.
🔗

🔗
State the Szemerédi Regularity Lemma.
🔗

🔗
State the Triangle Removal Lemma.
🔗

🔗
State the Ruzsa-Szemerédi corollary about graphs in which every edge is contained in exactly one triangle.
🔗

🔗
State the \((6,3)\)-Theorem.
🔗

🔗
State Roth’s Theorem.
🔗

🔗

🔗

Subsection 11.2.3 Proofs to be comfortable reproducing

Prove Mantel’s Theorem.
🔗

🔗
Explain the cloning or symmetrization proof strategy for Turán’s Theorem.
🔗

🔗
Prove that, for every graph \(H\text{,}\) the sequence \(\ex(n,H)/\binom{n}{2}\) is non-increasing.
🔗

🔗
Prove the Kövári-Sós-Turán Theorem using double-counting and convexity.
🔗

🔗
Prove that every graph \(G\) has a bipartite subgraph with at least \(|E(G)|/2\) edges.
🔗

🔗
Prove that every graph \(G\) has a subgraph with minimum degree at least \(|E(G)|/|V(G)|\text{.}\)
🔗

🔗
Prove Goodman’s Bound.
🔗

🔗
Prove that \(t(C_4,G)\geq t(K_2,G)^4\) for every graph \(G\text{.}\)
🔗

🔗
Use eigenvalues or closed walks to prove the even-cycle Sidorenko inequality covered in lecture.
🔗

🔗
Prove the Counting Lemma for triangles.
🔗

🔗
Show how the Regularity Lemma implies the Triangle Removal Lemma.
🔗

🔗
Explain the energy-increment proof of the Regularity Lemma, including the role of mean square density.
🔗

🔗

🔗

Subsection 11.2.4 Suggested exercises

For additional practice, work through exercises from the relevant sections of the notes.

🔗

Section 3.6 for Mantel’s Theorem, Turán’s Theorem, the Erdős-Stone Theorem and bipartite extremal numbers.
🔗

🔗
Section 4.7 for supersaturation, Goodman’s Bound, homomorphism densities and even cycles.
🔗

🔗
Section 5.4 for regular pairs, the Counting Lemma, the Szemerédi Regularity Lemma and the Triangle Removal Lemma.
🔗

🔗

🔗

Prev Top Next