Math 426/529: Extremal Combinatorics

Subsection 11.3.1 Additional definitions to know

1. Define an independent set and the independence number \(\alpha(G)\) of a graph \(G\text{.}\)

   🔗
   🔗
2. Define triangle-free graphs and \(d\)-regular graphs.

   🔗
   🔗
3. Define the range of a random variable.

   🔗
   🔗
4. Define the entropy \(H(X)\) of a discrete random variable with finite range.

   🔗
   🔗
5. Define conditional entropy \(H(X\mid Y)\text{.}\)

   🔗
   🔗
6. Explain what it means for random variables to be independent in the entropy setting.

   🔗
   🔗
7. Define a proper graph colouring and the number of proper \(q\)-colourings of a graph.

   🔗
   🔗
8. Define a perfect matching.

   🔗
   🔗
9. Define the permanent of a matrix.

   🔗
   🔗

Subsection 11.3.2 Additional theorem statements to know

1. State Shearer’s bound on the independence number of triangle-free graphs.

   🔗
   🔗
2. State Alon’s supersaturation lemma for independent sets in regular graphs.

   🔗
   🔗
3. State Alon’s theorem on the number of independent sets in a \(d\)-regular graph.

   🔗
   🔗
4. State the formula for the entropy of a uniform random variable.

   🔗
   🔗
5. State the chain rule of entropy.

   🔗
   🔗
6. State the deconditioning lemma for entropy.

   🔗
   🔗
7. State the fact that a random variable determined by another random variable has zero conditional entropy.

   🔗
   🔗
8. State Shearer’s Lemma.

   🔗
   🔗
9. State Han’s Inequality.

   🔗
   🔗
10. State the entropy bound for counting colourings of regular graphs.

    🔗
    🔗
11. State Brègman’s Theorem.

    🔗
    🔗
12. State the permanent formulation of Brègman’s Theorem.

    🔗
    🔗

Subsection 11.3.3 Proofs to be comfortable reproducing

1. Prove the probabilistic lower bound on the independence number of triangle-free graphs covered in lecture.

   🔗
   🔗
2. Prove that every triangle-free graph on \(n\) vertices has chromatic number \(O(\sqrt{n})\text{,}\) using an appropriate lower bound on independent sets.

   🔗
   🔗
3. Let \(G\) be a \(d\)-regular graph with \(n\) vertices. Prove that if \(S\subseteq V(G)\) and \(|S|\geq n/2+t\text{,}\) then there are at least \(td\) edges contained in \(S\text{.}\)

   🔗
   🔗
4. Explain the container-style counting argument leading to Alon’s theorem on independent sets in regular graphs.

   🔗
   🔗
5. Prove the basic entropy identities used in lecture: the chain rule, deconditioning and the zero conditional entropy lemma for determined variables.

   🔗
   🔗
6. Use entropy to prove the colouring bound for regular graphs covered in lecture.

   🔗
   🔗
7. Explain the proof strategy for Brègman’s Theorem and how it implies the permanent bound.

   🔗
   🔗

Subsection 11.3.4 Suggested exercises

• Section 6.5 for independent sets in triangle-free graphs, independent sets in regular graphs and the Dedekind’s problem.

  🔗
  🔗
• Section 7.6 for entropy, Shearer’s Lemma, counting colourings, permanents, perfect matchings and related topics.

  🔗
  🔗