Modern Graph Theory — Homework 2

Loading…

Modern Graph Theory — Homework 2

Assignments: Mar 10th, 2026

Problem 1.

\binom{n}{k}p^{\binom{k}{2}} + \binom{n}{t}(1-p)^{\binom{t}{2}} < 1 for some p \in [0,1], then the Ramsey number R(k,t) > n. **Proof.** We use the **probabilistic method**. Consider a random graph G \sim G(n,p) on n vertices where each edge appears independently with probability p. For any subset S \subseteq V(G) with |S| = k, let A_S be the event that S induces a k-clique (complete subgraph on k vertices). The probability of A_S is:

\Pr[A_S] = p^{\binom{k}{2}}

since all \binom{k}{2} edges within S must be present. Similarly, for any subset T \subseteq V(G) with |T| = t, let B_T be the event that T induces an independent set of size t. The probability of B_T is:

\Pr[B_T] = (1-p)^{\binom{t}{2}}

since all \binom{t}{2} edges within T must be absent. By the **union bound**, the probability that G contains either a k-clique or an independent set of size t is at most:

\sum{S:|S|=k} \Pr[AS] + \sum{T:|T|=t} \Pr[BT] = \binom{n}{k}p^{\binom{k}{2}} + \binom{n}{t}(1-p)^{\binom{t}{2}}

By assumption, this quantity is strictly less than 1. Therefore:

\Pr[G \text{ has no } k\text{-clique and no independent set of size } t] > 0

This means there exists at least one graph on n vertices with no k-clique and no independent set of size t. By definition of the Ramsey number, R(k,t) > n. ∎ **Problem 2.** For any graph G with 2n vertices and m edges, G contains a bipartite subgraph with at least \frac{mn}{2n-1} edges. **Proof.** Let G = (V,E) be a graph with |V| = 2n and |E| = m. We use a **probabilistic argument**. Consider a random bipartition of V into two sets A and B with |A| = |B| = n, chosen uniformly at random from all \binom{2n}{n} such bipartitions. For any edge e = \{u,v\} \in E, we compute the probability that e crosses the bipartition (i.e., u \in A, v \in B or u \in B, v \in A). Given edge e = \{u,v\}, we need to count bipartitions where u and v are in different parts. Fix u \in A and v \in B. We need to choose n-1 more vertices for A from the remaining 2n-2 vertices. The number of such bipartitions is \binom{2n-2}{n-1}. Similarly, if u \in B and v \in A, we also get \binom{2n-2}{n-1} bipartitions. Thus, the probability that edge e crosses the bipartition is:

\Pr[e \text{ crosses}] = \frac{2\binom{2n-2}{n-1}}{\binom{2n}{n}}

Simplifying:

\binom{2n}{n} = \frac{(2n)!}{n! \cdot n!} = \frac{2n \cdot (2n-1) \cdot (2n-2)!}{n \cdot (n-1)! \cdot n \cdot (n-1)!} = \frac{2n(2n-1)}{n^2} \binom{2n-2}{n-1} = \frac{2(2n-1)}{n} \binom{2n-2}{n-1}

Therefore:

\Pr[e \text{ crosses}] = \frac{2\binom{2n-2}{n-1}}{\frac{2(2n-1)}{n}\binom{2n-2}{n-1}} = \frac{n}{2n-1}

Let X be the random variable counting the number of crossing edges. By **linearity of expectation**:

\mathbb{E}[X] = \sum_{e \in E} \Pr[e \text{ crosses}] = m \cdot \frac{n}{2n-1} = \frac{mn}{2n-1}

Since \mathbb{E}[X] = \frac{mn}{2n-1}, there exists at least one bipartition with at least \frac{mn}{2n-1} crossing edges. These crossing edges form a bipartite subgraph. ∎ **Problem 3.** Prove that **Bollobás's Theorem** implies **Sperner's Theorem**. **Proof.** First, we state both theorems: **Theorem 1 (Sperner's Theorem, 1928).** Let \mathcal{F} be a family of subsets of [n] = \{1, 2, \ldots, n\} such that no set in \mathcal{F} contains another (i.e., \mathcal{F} is an antichain under inclusion). Then:

|\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor}

**Theorem 2 (Bollobás's Theorem, 1965).** Let A_1, \ldots, A_m and B_1, \ldots, B_m be subsets of [n] such that: - [(i)] A_i \cap B_i = \emptyset for all i \in [m]; - [(ii)] A_i \cap B_j \neq \emptyset for all i \neq j. Then:

\sum{i=1}^{m} \frac{1}{\binom{|Ai| + |Bi|}{|Ai|}} \leq 1

In particular, m \leq \binom{n}{\lfloor n/2 \rfloor}. Now we prove that Bollobás's Theorem implies Sperner's Theorem. Let \mathcal{F} = \{F_1, F_2, \ldots, F_m\} be an antichain on [n]. We will construct sets A_i and B_i satisfying the conditions of Bollobás's Theorem. For each i \in [m], define:

Ai = Fi \quad \text{and} \quad Bi = [n] \setminus Fi

We verify the conditions: - [(i)] A_i \cap B_i = F_i \cap ([n] \setminus F_i) = \emptyset for all i. \checkmark - [(ii)] For i \neq j, we need A_i \cap B_j \neq \emptyset, i.e., F_i \cap ([n] \setminus F_j) \neq \emptyset. This is equivalent to F_i \not\subseteq F_j. Since \mathcal{F} is an antichain, we have F_i \not\subseteq F_j for all i \neq j. \checkmark Now apply Bollobás's Theorem. Note that |A_i| + |B_i| = |F_i| + (n - |F_i|) = n for all i. Therefore:

\sum{i=1}^{m} \frac{1}{\binom{n}{|Fi|}} \leq 1

Since \binom{n}{k} is maximized at k = \lfloor n/2 \rfloor, we have \binom{n}{|F_i|} \leq \binom{n}{\lfloor n/2 \rfloor} for all i, which implies:

\frac{1}{\binom{n}{|F_i|}} \geq \frac{1}{\binom{n}{\lfloor n/2 \rfloor}}

Therefore:

\frac{m}{\binom{n}{\lfloor n/2 \rfloor}} = \sum{i=1}^{m} \frac{1}{\binom{n}{\lfloor n/2 \rfloor}} \leq \sum{i=1}^{m} \frac{1}{\binom{n}{|F_i|}} \leq 1

This gives m \leq \binom{n}{\lfloor n/2 \rfloor}, which is exactly Sperner's Theorem. ∎

PDF

Download the original write-up here.

Assignments: Mar 10th, 2026

Problem 1.

\binom{n}{k}p^{\binom{k}{2}} + \binom{n}{t}(1-p)^{\binom{t}{2}} < 1 for some p \in [0,1], then the Ramsey number R(k,t) > n. **Proof.** We use the **probabilistic method**. Consider a random graph G \sim G(n,p) on n vertices where each edge appears independently with probability p. For any subset S \subseteq V(G) with |S| = k, let A_S be the event that S induces a k-clique (complete subgraph on k vertices). The probability of A_S is:

\Pr[A_S] = p^{\binom{k}{2}}

since all \binom{k}{2} edges within S must be present. Similarly, for any subset T \subseteq V(G) with |T| = t, let B_T be the event that T induces an independent set of size t. The probability of B_T is:

\Pr[B_T] = (1-p)^{\binom{t}{2}}

since all \binom{t}{2} edges within T must be absent. By the **union bound**, the probability that G contains either a k-clique or an independent set of size t is at most:

\sum{S:|S|=k} \Pr[AS] + \sum{T:|T|=t} \Pr[BT] = \binom{n}{k}p^{\binom{k}{2}} + \binom{n}{t}(1-p)^{\binom{t}{2}}

By assumption, this quantity is strictly less than 1. Therefore:

\Pr[G \text{ has no } k\text{-clique and no independent set of size } t] > 0

This means there exists at least one graph on n vertices with no k-clique and no independent set of size t. By definition of the Ramsey number, R(k,t) > n. ∎ **Problem 2.** For any graph G with 2n vertices and m edges, G contains a bipartite subgraph with at least \frac{mn}{2n-1} edges. **Proof.** Let G = (V,E) be a graph with |V| = 2n and |E| = m. We use a **probabilistic argument**. Consider a random bipartition of V into two sets A and B with |A| = |B| = n, chosen uniformly at random from all \binom{2n}{n} such bipartitions. For any edge e = \{u,v\} \in E, we compute the probability that e crosses the bipartition (i.e., u \in A, v \in B or u \in B, v \in A). Given edge e = \{u,v\}, we need to count bipartitions where u and v are in different parts. Fix u \in A and v \in B. We need to choose n-1 more vertices for A from the remaining 2n-2 vertices. The number of such bipartitions is \binom{2n-2}{n-1}. Similarly, if u \in B and v \in A, we also get \binom{2n-2}{n-1} bipartitions. Thus, the probability that edge e crosses the bipartition is:

\Pr[e \text{ crosses}] = \frac{2\binom{2n-2}{n-1}}{\binom{2n}{n}}

Simplifying:

\binom{2n}{n} = \frac{(2n)!}{n! \cdot n!} = \frac{2n \cdot (2n-1) \cdot (2n-2)!}{n \cdot (n-1)! \cdot n \cdot (n-1)!} = \frac{2n(2n-1)}{n^2} \binom{2n-2}{n-1} = \frac{2(2n-1)}{n} \binom{2n-2}{n-1}

Therefore:

\Pr[e \text{ crosses}] = \frac{2\binom{2n-2}{n-1}}{\frac{2(2n-1)}{n}\binom{2n-2}{n-1}} = \frac{n}{2n-1}

Let X be the random variable counting the number of crossing edges. By **linearity of expectation**:

\mathbb{E}[X] = \sum_{e \in E} \Pr[e \text{ crosses}] = m \cdot \frac{n}{2n-1} = \frac{mn}{2n-1}

Since \mathbb{E}[X] = \frac{mn}{2n-1}, there exists at least one bipartition with at least \frac{mn}{2n-1} crossing edges. These crossing edges form a bipartite subgraph. ∎ **Problem 3.** Prove that **Bollobás's Theorem** implies **Sperner's Theorem**. **Proof.** First, we state both theorems: **Theorem 1 (Sperner's Theorem, 1928).** Let \mathcal{F} be a family of subsets of [n] = \{1, 2, \ldots, n\} such that no set in \mathcal{F} contains another (i.e., \mathcal{F} is an antichain under inclusion). Then:

|\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor}

**Theorem 2 (Bollobás's Theorem, 1965).** Let A_1, \ldots, A_m and B_1, \ldots, B_m be subsets of [n] such that: - [(i)] A_i \cap B_i = \emptyset for all i \in [m]; - [(ii)] A_i \cap B_j \neq \emptyset for all i \neq j. Then:

\sum{i=1}^{m} \frac{1}{\binom{|Ai| + |Bi|}{|Ai|}} \leq 1

In particular, m \leq \binom{n}{\lfloor n/2 \rfloor}. Now we prove that Bollobás's Theorem implies Sperner's Theorem. Let \mathcal{F} = \{F_1, F_2, \ldots, F_m\} be an antichain on [n]. We will construct sets A_i and B_i satisfying the conditions of Bollobás's Theorem. For each i \in [m], define:

Ai = Fi \quad \text{and} \quad Bi = [n] \setminus Fi

We verify the conditions: - [(i)] A_i \cap B_i = F_i \cap ([n] \setminus F_i) = \emptyset for all i. \checkmark - [(ii)] For i \neq j, we need A_i \cap B_j \neq \emptyset, i.e., F_i \cap ([n] \setminus F_j) \neq \emptyset. This is equivalent to F_i \not\subseteq F_j. Since \mathcal{F} is an antichain, we have F_i \not\subseteq F_j for all i \neq j. \checkmark Now apply Bollobás's Theorem. Note that |A_i| + |B_i| = |F_i| + (n - |F_i|) = n for all i. Therefore:

\sum{i=1}^{m} \frac{1}{\binom{n}{|Fi|}} \leq 1

Since \binom{n}{k} is maximized at k = \lfloor n/2 \rfloor, we have \binom{n}{|F_i|} \leq \binom{n}{\lfloor n/2 \rfloor} for all i, which implies:

\frac{1}{\binom{n}{|F_i|}} \geq \frac{1}{\binom{n}{\lfloor n/2 \rfloor}}

Therefore:

\frac{m}{\binom{n}{\lfloor n/2 \rfloor}} = \sum{i=1}^{m} \frac{1}{\binom{n}{\lfloor n/2 \rfloor}} \leq \sum{i=1}^{m} \frac{1}{\binom{n}{|F_i|}} \leq 1

This gives m \leq \binom{n}{\lfloor n/2 \rfloor}, which is exactly Sperner's Theorem. ∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 2

Search

Modern Graph Theory — Homework 2

Assignments: Mar 10th, 2026

PDF

Assignments: Mar 10th, 2026

PDF