Modern Graph Theory — Homework 10

Loading…

Modern Graph Theory — Homework 10

Assignments: May 19th, 2026

Problem 1.

Prove: Let

G be a bipartite graph with a partition (A,B) such that |A|=|B|=n and

e(G)=\frac{n^2}{2}-1.

The graph G contains a subgraph K_{\frac{n}{2},\frac{n}{2}} if and only if (A,B) is not a \frac12-regular pair. **Proof.** We assume that n is even.

d(X,Y)=\frac{e(X,Y)}{|X||Y|}.

The density of the whole pair is

d(A,B)=\frac{e(G)}{n^2}=\frac12-\frac{1}{n^2}.

First, we suppose that G contains a copy of K_{\frac{n}{2},\frac{n}{2}}. Let its two vertex classes be X\subseteq A and Y\subseteq B, where |X|=|Y|=\frac n2. Then d(X,Y)=1, and hence

|d(X,Y)-d(A,B)|

=1-\left(\frac12-\frac{1}{n^2}\right) =\frac12+\frac{1}{n^2}

\frac12.

Thus (A,B) is not \frac12-regular. Conversely, suppose that (A,B) is not \frac12-regular. Then there exist X\subseteq A and Y\subseteq B with

|X|\ge \frac n2,\qquad |Y|\ge \frac n2

such that

|d(X,Y)-d(A,B)|\ge \frac12.

Since d(A,B)<\frac12 and d(X,Y)\ge 0, the deviation cannot occur below d(A,B). Therefore

d(X,Y)-d(A,B)\ge\frac12,

and so

d(X,Y)\ge 1-\frac{1}{n^2}.

We claim that (X,Y) must be complete. If one edge between X and Y were missing, then

d(X,Y)\le 1-\frac{1}{|X||Y|} \le 1-\frac{1}{n^2},

so equality would have to hold throughout. This would force |X||Y|=n^2, hence X=A and Y=B. But then d(X,Y)=d(A,B), which does not give a deviation of \frac12. Therefore (X,Y) is complete. Since |X|,|Y|\ge \frac n2, we may choose \frac n2 vertices from each side and obtain a copy of K_{\frac{n}{2},\frac{n}{2}}. ∎ **Problem 2.** (Chernoff Bound). Let X_1,\ldots,X_n be independent indicator variables such that \Pr[X_i=1]=p for each i\in[n]. Let X=\sum_{i=1}^n X_i. We know that

\Pr[|X-\mathbb{E}(X)|>\alpha]\le 2e^{-\frac{2\alpha^2}{n}}.

Let G(A,B,p) denote a random bipartite graph on two disjoint vertex sets A,B with |A|=|B|=n such that for each a\in A and b\in B, ab is chosen to be an edge with probability p independently. Prove: For any \epsilon>0, G(A,B,p) is \epsilon-regular with probability tending to 1 as n tends to infinity. **Proof.** Consider 0<\epsilon<1, Set

\eta=\frac{\epsilon}{3}.

For fixed subsets X\subseteq A and Y\subseteq B, the random variable e(X,Y) is a sum of |X||Y| independent indicator variables, and

\mathbb{E}[e(X,Y)]=p|X||Y|.

Applying the given Chernoff bound with \alpha=\eta|X||Y|, we get

\Pr\bigl[|d(X,Y)-p|>\eta\bigr] \le 2e^{-2\eta^2|X||Y|}.

Now restrict to pairs (X,Y) satisfying

|X|\ge \epsilon n,\qquad |Y|\ge \epsilon n.

For each such pair, |X||Y|\ge \epsilon^2n^2, and therefore

\Pr\bigl[|d(X,Y)-p|>\eta\bigr] \le 2e^{-2\eta^2\epsilon^2n^2}.

There are at most 2^n choices for X and at most 2^n choices for Y. Hence, by the union bound, the probability that some such pair satisfies |d(X,Y)-p|>\eta is at most

2\cdot 4^n e^{-2\eta^2\epsilon^2n^2}=o(1).

Thus, with probability tending to 1, every pair (X,Y) with |X|,|Y|\ge \epsilon n satisfies

|d(X,Y)-p|\le \eta.

This also holds for the whole pair (A,B). Hence for every such X,Y,

|d(X,Y)-d(A,B)|

\le |d(X,Y)-p|+|d(A,B)-p| \le 2\eta <\epsilon.

Therefore G(A,B,p) is \epsilon-regular with probability tending to 1. ∎

PDF

Download the original write-up here.

Assignments: May 19th, 2026

Problem 1.

Prove: Let

G be a bipartite graph with a partition (A,B) such that |A|=|B|=n and

e(G)=\frac{n^2}{2}-1.

The graph G contains a subgraph K_{\frac{n}{2},\frac{n}{2}} if and only if (A,B) is not a \frac12-regular pair. **Proof.** We assume that n is even.

d(X,Y)=\frac{e(X,Y)}{|X||Y|}.

The density of the whole pair is

d(A,B)=\frac{e(G)}{n^2}=\frac12-\frac{1}{n^2}.

First, we suppose that G contains a copy of K_{\frac{n}{2},\frac{n}{2}}. Let its two vertex classes be X\subseteq A and Y\subseteq B, where |X|=|Y|=\frac n2. Then d(X,Y)=1, and hence

|d(X,Y)-d(A,B)|

=1-\left(\frac12-\frac{1}{n^2}\right) =\frac12+\frac{1}{n^2}

\frac12.

Thus (A,B) is not \frac12-regular. Conversely, suppose that (A,B) is not \frac12-regular. Then there exist X\subseteq A and Y\subseteq B with

|X|\ge \frac n2,\qquad |Y|\ge \frac n2

such that

|d(X,Y)-d(A,B)|\ge \frac12.

Since d(A,B)<\frac12 and d(X,Y)\ge 0, the deviation cannot occur below d(A,B). Therefore

d(X,Y)-d(A,B)\ge\frac12,

and so

d(X,Y)\ge 1-\frac{1}{n^2}.

We claim that (X,Y) must be complete. If one edge between X and Y were missing, then

d(X,Y)\le 1-\frac{1}{|X||Y|} \le 1-\frac{1}{n^2},

so equality would have to hold throughout. This would force |X||Y|=n^2, hence X=A and Y=B. But then d(X,Y)=d(A,B), which does not give a deviation of \frac12. Therefore (X,Y) is complete. Since |X|,|Y|\ge \frac n2, we may choose \frac n2 vertices from each side and obtain a copy of K_{\frac{n}{2},\frac{n}{2}}. ∎ **Problem 2.** (Chernoff Bound). Let X_1,\ldots,X_n be independent indicator variables such that \Pr[X_i=1]=p for each i\in[n]. Let X=\sum_{i=1}^n X_i. We know that

\Pr[|X-\mathbb{E}(X)|>\alpha]\le 2e^{-\frac{2\alpha^2}{n}}.

Let G(A,B,p) denote a random bipartite graph on two disjoint vertex sets A,B with |A|=|B|=n such that for each a\in A and b\in B, ab is chosen to be an edge with probability p independently. Prove: For any \epsilon>0, G(A,B,p) is \epsilon-regular with probability tending to 1 as n tends to infinity. **Proof.** Consider 0<\epsilon<1, Set

\eta=\frac{\epsilon}{3}.

For fixed subsets X\subseteq A and Y\subseteq B, the random variable e(X,Y) is a sum of |X||Y| independent indicator variables, and

\mathbb{E}[e(X,Y)]=p|X||Y|.

Applying the given Chernoff bound with \alpha=\eta|X||Y|, we get

\Pr\bigl[|d(X,Y)-p|>\eta\bigr] \le 2e^{-2\eta^2|X||Y|}.

Now restrict to pairs (X,Y) satisfying

|X|\ge \epsilon n,\qquad |Y|\ge \epsilon n.

For each such pair, |X||Y|\ge \epsilon^2n^2, and therefore

\Pr\bigl[|d(X,Y)-p|>\eta\bigr] \le 2e^{-2\eta^2\epsilon^2n^2}.

There are at most 2^n choices for X and at most 2^n choices for Y. Hence, by the union bound, the probability that some such pair satisfies |d(X,Y)-p|>\eta is at most

2\cdot 4^n e^{-2\eta^2\epsilon^2n^2}=o(1).

Thus, with probability tending to 1, every pair (X,Y) with |X|,|Y|\ge \epsilon n satisfies

|d(X,Y)-p|\le \eta.

This also holds for the whole pair (A,B). Hence for every such X,Y,

|d(X,Y)-d(A,B)|

\le |d(X,Y)-p|+|d(A,B)-p| \le 2\eta <\epsilon.

Therefore G(A,B,p) is \epsilon-regular with probability tending to 1. ∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 10

Search

Modern Graph Theory — Homework 10

Assignments: May 19th, 2026

PDF

Assignments: May 19th, 2026

PDF