Modern Graph Theory — Homework 3

Loading…

Assignments: Mar 17th, 2026

Problem 1.

2-edge-coloring of K_n with at most \binom{n}{k}2^{1-\binom{k}{2}} monochromatic K_k. 2. Prove: R(k,k) > n - \binom{n}{k}2^{1-\binom{k}{2}}. **Proof.** **(a)** Consider a random 2-edge-coloring of K_n where each edge is colored independently with red or blue, each with probability \frac{1}{2}. For any subset S \subseteq V(K_n) with |S| = k, let X_S be the indicator random variable for the event that S induces a monochromatic K_k. The probability that all \binom{k}{2} edges within S are the same color is:

\Pr[X_S = 1] = 2 \cdot \left(\frac{1}{2}\right)^{\binom{k}{2}} = 2^{1-\binom{k}{2}}

since there are 2 choices for the color (red or blue) and each edge has probability \frac{1}{2} of being that color. Let X be the total number of monochromatic K_k subgraphs. And then, we have:

\mathbb{E}[X] = \sum{S:|S|=k} \mathbb{E}[XS] = \binom{n}{k} \cdot 2^{1-\binom{k}{2}}

Since the expected number of monochromatic K_k is \binom{n}{k}2^{1-\binom{k}{2}}.In other word, there must exist at least one 2-edge-coloring of K_n with at most this many monochromatic K_k. **(b)** Let N = \binom{n}{k}2^{1-\binom{k}{2}}. From (a) we know that there exists a 2-edge-coloring of K_n with at most N monochromatic K_k. For each monochromatic K_k, we delete one vertex. Since there are at most N monochromatic K_k, we delete at most N vertices in total. Let G' be the resulting graph on at least n - N vertices. By construction, G' has no monochromatic K_k in either color, because we removed at least one vertex from every monochromatic K_k that existed in the original coloring. Therefore, there exists a 2-edge-coloring of K_{n-N} with no monochromatic K_k, which implies:

R(k,k) > n - N = n - \binom{n}{k}2^{1-\binom{k}{2}}

∎ **Problem 2.** A **tournament** T_n = (V, D) is an oriented complete graph, i.e., V = [n] and for any two vertices u, v \in V, either (u,v) \in D or (v,u) \in D. A **Hamiltonian path** of T_n is a sequence of vertices i_1, i_2, \ldots, i_n such that all i_j's are distinct elements of [n] and for each k \in \{1, 2, \ldots, n-1\}, (i_k, i_{k+1}) \in D. Prove: There is a tournament T_n with at least n!2^{-(n-1)} Hamiltonian paths. **Proof.** Consider a random tournament T_n on vertex set [n], where for each pair of distinct vertices \{u,v\}, the edge orientation is chosen independently and uniformly at random (i.e., (u,v) \in D with probability \frac{1}{2} and (v,u) \in D with probability \frac{1}{2}). For any permutation \pi = (i_1, i_2, \ldots, i_n) of [n], let X_\pi be the indicator random variable for the event that \pi forms a Hamiltonian path in T_n. That is:

X\pi = \mathbf{1}{{(ik, i{k+1}) \in D \text{ for all } k = 1, \ldots, n-1}}

For \pi to be a Hamiltonian path, we need all n-1 directed edges (i_1, i_2), (i_2, i_3), \ldots, (i_{n-1}, i_n) to be present in T_n. Since each edge orientation is chosen independently with probability \frac{1}{2}:

\Pr[X_\pi = 1] = \left(\frac{1}{2}\right)^{n-1} = 2^{-(n-1)}

Let X be the total number of Hamiltonian paths in T_n. We have:

\mathbb{E}[X] = \sum{\pi \in Sn} \mathbb{E}[X_\pi] = n! \cdot 2^{-(n-1)}

where S_n denotes the set of all n! permutations of [n]. Since \mathbb{E}[X] = n!2^{-(n-1)}, there must exist at least one tournament T_n with at least n!2^{-(n-1)} Hamiltonian paths. ∎

Download the original write-up here.