Math 426/529: Extremal Combinatorics

Subsection 11.1.1 Definitions to know

1. Define what it means for a set system \(\mathcal{F}\subseteq 2^{[n]}\) to be intersecting.

   🔗
   🔗
2. Define a sunflower. Include the definitions of core and petals.

   🔗
   🔗
3. Define what it means for a set system \(\mathcal{F}\subseteq 2^{[n]}\) to shatter a set \(X\subseteq [n]\text{.}\)

   🔗
   🔗
4. Define the VC-dimension of a set system.

   🔗
   🔗
5. Define downsets and upsets.

   🔗
   🔗
6. Define an antichain in \(2^{[n]}\text{.}\)

   🔗
   🔗
7. Define a chain in \(2^{[n]}\text{.}\)

   🔗
   🔗
8. Define a symmetric chain in \(2^{[n]}\text{.}\)

   🔗
   🔗
9. For \(\mathcal{F}\subseteq \binom{[n]}{k}\text{,}\) define the shadow \(\partial \mathcal{F}\text{.}\)

   🔗
   🔗
10. Define colexicographic order on \(\binom{\mathbb{N}}{k}\text{.}\)

    🔗
    🔗
11. Define lexicographic order on \(\binom{\mathbb{N}}{k}\text{.}\)

    🔗
    🔗
12. For distinct \(i,j\in\mathbb{N}\text{,}\) define the \((i,j)\)-compression operation \(C_{i,j}\) on subsets of \(\mathbb{N}\text{,}\) and define the compression of a set system.

    🔗
    🔗
13. Explain the meanings of \(f\sim g\), \(f=O(g)\), \(f=o(g)\), \(f=\Omega(g)\) and \(f=\Theta(g)\).

    🔗
    🔗

Subsection 11.1.2 Theorem statements to know

1. State the Erdős-Ko-Rado Theorem.

   🔗
   🔗
2. State the Sunflower Lemma.

   🔗
   🔗
3. State the Sauer-Shelah Lemma.

   🔗
   🔗
4. State the Harris-Kleitman Inequality.

   🔗
   🔗
5. State Lovász’s theorem on partitions of \(\binom{[n]}{k}\) into intersecting families.

   🔗
   🔗
6. State Sperner’s Theorem.

   🔗
   🔗
7. State the symmetric chain decomposition lemma for \(2^{[n]}\text{.}\)

   🔗
   🔗
8. State the LYM Inequality.

   🔗
   🔗
9. State the Local LYM Inequality.

   🔗
   🔗
10. State Erdős’s theorem on families with no chain of length \(k+1\text{.}\)

    🔗
    🔗
11. State the Kruskal-Katona Theorem.

    🔗
    🔗
12. State the corollary saying what Kruskal-Katona gives when \(\mathcal{F}\subseteq \binom{[n]}{k}\) and \(|\mathcal{F}|=\binom{m}{k}\text{.}\)

    🔗
    🔗
13. State Kleitman’s theorem on the Littlewood-Offord problem.

    🔗
    🔗
14. State Jensen’s Inequality and Hölder’s Inequality.

    🔗
    🔗

Subsection 11.1.3 Proofs to be comfortable reproducing

1. Prove the Sunflower Lemma.

   🔗
   🔗
2. Prove the Sauer-Shelah Lemma.

   🔗
   🔗
3. Prove the Harris-Kleitman Inequality.

   🔗
   🔗
4. Prove that, if \(\mathcal{A}\) is an antichain and \(\mathcal{C}\) is a chain, then \(|\mathcal{A}\cap\mathcal{C}|\leq 1\text{.}\)

   🔗
   🔗
5. Assume that \(2^{[n]}\) has a symmetric chain decomposition and use it to prove Sperner’s Theorem.

   🔗
   🔗
6. Prove the LYM Inequality.

   🔗
   🔗
7. Use the LYM Inequality to prove the Local LYM Inequality.

   🔗
   🔗
8. Let \(A=\{a_1,\ldots,a_k\}\) with \(a_1\lt a_2\lt\cdots\lt a_k\text{.}\) Derive the formula for the number of sets in \(\binom{\mathbb{N}}{k}\) which come before \(A\) in colex order.

   🔗
   🔗
9. Use the Kruskal-Katona Theorem to prove the Erdős-Ko-Rado Theorem.

   🔗
   🔗
10. Prove the Littlewood-Offord theorem for \(\mathbb{R}\text{.}\)

    🔗
    🔗

Subsection 11.1.4 Suggested exercises

• Section 1.6 for intersecting families, the Erdős-Ko-Rado Theorem, sunflowers, VC-dimension and the Harris-Kleitman Inequality.

  🔗
  🔗
• Section A.1 and Section C.1 for asymptotic notation and convexity.

  🔗
  🔗
• Section 2.5 for chains and antichains, including Sperner’s Theorem, the LYM Inequality, Kruskal-Katona and Littlewood-Offord.

  🔗
  🔗