Modern Graph Theory — Homework 6

Loading…

Modern Graph Theory — Homework 6

Assignments: Apr 7th, 2026

Problem 1.

Let

\pi_n(H) := \frac{ex(n,H)}{\binom{n}{2}} and let \pi(H) := \lim_{n \to +\infty} \pi_n(H). Use the Probabilistic Method to prove that \pi_n(H) is non-increasing as n increases. **Proof.** Let G be an n-vertex H-free graph with ex(n,H) edges. Pick a vertex v \in V(G) uniformly at random and delete it. The resulting graph G' has n-1 vertices. The expected number of edges in G' is

\mathbb{E}[e(G')] = e(G) - \frac{1}{n}\sum_{v \in V(G)} \deg(v) = e(G) - \frac{2e(G)}{n} = e(G) \cdot \frac{n-2}{n}.

Since G' is H-free, we have e(G') \leq ex(n-1,H). Taking expectations,

ex(n,H) \cdot \frac{n-2}{n} \leq ex(n-1,H).

Rearranging,

\frac{ex(n,H)}{\binom{n}{2}} = \frac{ex(n,H)}{\frac{n(n-1)}{2}} \leq \frac{ex(n-1,H)}{\frac{(n-1)(n-2)}{2}} = \frac{ex(n-1,H)}{\binom{n-1}{2}}.

Thus \pi_n(H) \leq \pi_{n-1}(H), so \pi_n(H) is non-increasing in n. ∎ **Problem 2.** Let X be a set of n points on a circle of radius 1. Then the number of pairs of distinct points in X whose Euclidean distance exceeds \sqrt{3} is at most \left\lfloor \frac{n^2}{4} \right\rfloor. Moreover, this bound is tight. **Proof.** Two points on a unit circle have distance greater than \sqrt{3} if and only if the central angle between them exceeds 2\pi/3 (since d = 2\sin(\theta/2) > \sqrt{3} implies \theta > 2\pi/3). Define a graph G on vertex set X where two points are adjacent if their distance exceeds \sqrt{3}. We claim **G is triangle-free**. Indeed, three points with pairwise distances all exceeding \sqrt{3} would have pairwise central angles all exceeding 2\pi/3, but 3 \cdot (2\pi/3) = 2\pi, so such a configuration is impossible on a circle. By **Tur\'an's theorem**, e(G) \leq \lfloor n^2/4 \rfloor, with equality if and only if G is a complete bipartite graph with parts as equal as possible. Then we claim **this bound is tight**. Let \varepsilon \in (0,\pi/6). Place \lfloor n/2 \rfloor points on the short arc with angles in [-\varepsilon,\varepsilon], and place the remaining \lceil n/2 \rceil points on the opposite short arc with angles in [\pi-\varepsilon,\pi+\varepsilon]. For any two points chosen from different arcs, the central angle between them is at least \pi-2\varepsilon > 2\pi/3, hence their distance is greater than \sqrt{3}. Therefore every cross pair is counted, giving exactly

\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \left\lfloor \frac{n^2}{4} \right\rfloor,

so the upper bound is attained. ∎

PDF

Download the original write-up here.

Assignments: Apr 7th, 2026

Problem 1.

Let

\pi_n(H) := \frac{ex(n,H)}{\binom{n}{2}} and let \pi(H) := \lim_{n \to +\infty} \pi_n(H). Use the Probabilistic Method to prove that \pi_n(H) is non-increasing as n increases. **Proof.** Let G be an n-vertex H-free graph with ex(n,H) edges. Pick a vertex v \in V(G) uniformly at random and delete it. The resulting graph G' has n-1 vertices. The expected number of edges in G' is

\mathbb{E}[e(G')] = e(G) - \frac{1}{n}\sum_{v \in V(G)} \deg(v) = e(G) - \frac{2e(G)}{n} = e(G) \cdot \frac{n-2}{n}.

Since G' is H-free, we have e(G') \leq ex(n-1,H). Taking expectations,

ex(n,H) \cdot \frac{n-2}{n} \leq ex(n-1,H).

Rearranging,

\frac{ex(n,H)}{\binom{n}{2}} = \frac{ex(n,H)}{\frac{n(n-1)}{2}} \leq \frac{ex(n-1,H)}{\frac{(n-1)(n-2)}{2}} = \frac{ex(n-1,H)}{\binom{n-1}{2}}.

Thus \pi_n(H) \leq \pi_{n-1}(H), so \pi_n(H) is non-increasing in n. ∎ **Problem 2.** Let X be a set of n points on a circle of radius 1. Then the number of pairs of distinct points in X whose Euclidean distance exceeds \sqrt{3} is at most \left\lfloor \frac{n^2}{4} \right\rfloor. Moreover, this bound is tight. **Proof.** Two points on a unit circle have distance greater than \sqrt{3} if and only if the central angle between them exceeds 2\pi/3 (since d = 2\sin(\theta/2) > \sqrt{3} implies \theta > 2\pi/3). Define a graph G on vertex set X where two points are adjacent if their distance exceeds \sqrt{3}. We claim **G is triangle-free**. Indeed, three points with pairwise distances all exceeding \sqrt{3} would have pairwise central angles all exceeding 2\pi/3, but 3 \cdot (2\pi/3) = 2\pi, so such a configuration is impossible on a circle. By **Tur\'an's theorem**, e(G) \leq \lfloor n^2/4 \rfloor, with equality if and only if G is a complete bipartite graph with parts as equal as possible. Then we claim **this bound is tight**. Let \varepsilon \in (0,\pi/6). Place \lfloor n/2 \rfloor points on the short arc with angles in [-\varepsilon,\varepsilon], and place the remaining \lceil n/2 \rceil points on the opposite short arc with angles in [\pi-\varepsilon,\pi+\varepsilon]. For any two points chosen from different arcs, the central angle between them is at least \pi-2\varepsilon > 2\pi/3, hence their distance is greater than \sqrt{3}. Therefore every cross pair is counted, giving exactly

\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil = \left\lfloor \frac{n^2}{4} \right\rfloor,

so the upper bound is attained. ∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 6

Search

Modern Graph Theory — Homework 6

Assignments: Apr 7th, 2026

PDF

Assignments: Apr 7th, 2026

PDF