Modern Graph Theory — Homework 7

Loading…

Modern Graph Theory — Homework 7

Assignments: Apr 21st, 2026

Review

Theorem 1 (Erdős--Renyi--Sői,1966;Brown,1966;Balogh--Joself,2010).

(\frac{1}{2}-o(1))n^{\frac{3}{2}}\leq ex(n,C_4)\leq \frac{1}{4}(1+(4n-3)^{\frac{1}{2}})n^{\frac{3}{2}}=(\frac{1}{2}+o(1))n^{\frac{3}{2}}

Definition 1 (labeled fork).

Let

F be the set of **labeled forks**,

F=\left{(u,v,w)|uv,uw\in E(G),v\neq w\right}

**Remark 1.** One "labeled" point connects two different point on the graph.Just like a **fork**. **Theorem 2 (Kőv\'ari--S\'os--Tur\'an theorem).** For \forall t\geq s\geq 2,

ex(n,K_{s,t})\leq\frac{1}{2}(t-1)^{\frac{1}{2}}n^{2-\frac{1}{s}}+\frac{1}{2}(s-1)n=O(n^{1-\frac{1}{s}})

**Remark 2.** Last definition is **BFS Tree Method**, which is systematic algorithm for exploring every node in a tree data structure level by level.

Homework

Problem 1.

Prove: Every $n$ -vertex graph with at least $2ex(n,C_4)$ edges contains at least $(\frac{3}{2}-o(1))n^2$ many copies of $C_4$ .

Proof.

Let $G$ be an $n$ -vertex graph with $m=e(G)\ge 2ex(n,C_4)$ . For distinct vertices $x,y$ , we note

N_{xy}:=|N(x)\cap N(y)|.

Define a labeled fork to be an ordered triple $(x,z,y)$ with $x\neq y$ and $xz,zy\in E(G)$ . Let $F$ be the number of labeled forks.

Counting by the center $z$ :

F=\sum_{z\in V(G)} d(z)(d(z)-1).

By Jensen Inequality,

F\ge n\left(\frac{2m}{n}\right)\left(\frac{2m}{n}-1\right)=\frac{4m^2}{n}-2m.

By Theorem 1, we get

m\ge 2ex(n,C_4)=(1+o(1))n^{3/2},

hence

F\ge (4-o(1))n^2.

Counting forks by endpoints:

F=\sum_{x\neq y} N_{xy}=2\sum_{\{x,y\}\in \binom{V}{2}} N_{xy},

\sum_{\{x,y\}} N_{xy}\ge (2-o(1))n^2.

Let $N=\binom{n}{2}=(\frac12+o(1))n^2$ . By convexity of $u\mapsto \binom{u}{2}$ ,

\sum_{\{x,y\}}\binom{N_{xy}}{2} \ge N\binom{\frac{1}{N}\sum_{\{x,y\}}N_{xy}}{2} \ge N\binom{4-o(1)}{2} =(3-o(1))n^2.

Now $\sum_{\{x,y\}}\binom{N_{xy}}{2}$ counts each $C_4$ exactly twice (once for each pair of opposite vertices). Therefore

\#C_4(G)\ge \frac12(3-o(1))n^2 =\left(\frac32-o(1)\right)n^2.

∎

Problem 2.

Prove: Every set of $n$ points in the Euclidean plane $\mathbb{R}^2$ has at most $O(n^{3/2})$ unit distances.

Proof.

Let $P$ be the $n$ -point set, and build a graph $G$ on vertex set $P$ by joining two points iff their Euclidean distance is $1$ . Then $e(G)$ is exactly the number of unit distances.

We claim $G$ is $K_{2,3}$ -free. Indeed, if two points $a,b$ had three common neighbors $x_1,x_2,x_3$ , then each $x_i$ would lie on both unit circles centered at $a$ and $b$ . But two distinct circles intersect in at most two points, contradiction.

Hence $e(G)\le ex(n,K_{2,3})$ . By Theorem 2,

ex(n,K_{2,3})\le (3-1)^{1/2}n^{3/2}+(2-1)n=\sqrt{2}\,n^{3/2}+n=O(n^{3/2}).

Therefore the number of unit distances is $O(n^{3/2})$ .

∎

Problem 3.

Prove: For fixed $k\ge 2$ , there exists a constant $c_k$ such that

ex\!\left(n,\mathcal{C}_{\le 2k}^{e}\right)\le c_k n^{1+1/k}, \qquad \mathcal{C}_{\le 2k}^{e}=\{C_4,C_6,\dots,C_{2k}\}.

Proof.

Let $G$ be an $n$ -vertex graph with no even cycle of length at most $2k$ , and let $m=e(G)$ .

Take a bipartite subgraph $H\subseteq G$ with at least $m/2$ edges. Then $H$ is still $\mathcal{C}_{\le 2k}^{e}$ -free. Since $H$ is bipartite, all its cycles are even, so in fact $H$ has no cycle of length $\le 2k$ , i.e. girth $(H)>2k$ .

Let $n_H=|V(H)|\le n$ , and $d=2e(H)/n_H$ be the average degree of $H$ . By repeatedly deleting vertices of degree $<d/2$ , we get a nonempty subgraph $H'\subseteq H$ with minimum degree

\delta(H')\ge d/2.

Also girth $(H')>2k$ .

Pick $v\in V(H')$ and run BFS: levels $L_0=\{v\},L_1,\dots,L_k$ . Because girth is $>2k$ , the ball of radius $k$ is tree-like, hence

|L_1|\ge \delta,\qquad |L_i|\ge (\delta-1)|L_{i-1}| \ (2\le i\le k),

where $\delta=\delta(H')$ . Therefore

n\ge n_H\ge |V(H')| \ge 1+\delta\sum_{i=0}^{k-1}(\delta-1)^i \ge (\delta-1)^k.

So $\delta\le n^{1/k}+1$ , and thus

d\le 2\delta\le 2n^{1/k}+2.

Hence

e(H)=\frac{dn_H}{2}\le \frac{dn}{2}\le n^{1+1/k}+n.

Finally,

m\le 2e(H)\le 2n^{1+1/k}+2n\le 4n^{1+1/k}.

So we may take $c_k=4$ and has

ex\!\left(n,\mathcal{C}_{\le 2k}^{e}\right)\le c_k n^{1+1/k}.

∎

PDF

Download the original write-up here.

Assignments: Apr 21st, 2026

Review

Theorem 1 (Erdős--Renyi--Sői,1966;Brown,1966;Balogh--Joself,2010).

(\frac{1}{2}-o(1))n^{\frac{3}{2}}\leq ex(n,C_4)\leq \frac{1}{4}(1+(4n-3)^{\frac{1}{2}})n^{\frac{3}{2}}=(\frac{1}{2}+o(1))n^{\frac{3}{2}}

Definition 1 (labeled fork).

Let

F be the set of **labeled forks**,

F=\left{(u,v,w)|uv,uw\in E(G),v\neq w\right}

**Remark 1.** One "labeled" point connects two different point on the graph.Just like a **fork**. **Theorem 2 (Kőv\'ari--S\'os--Tur\'an theorem).** For \forall t\geq s\geq 2,

ex(n,K_{s,t})\leq\frac{1}{2}(t-1)^{\frac{1}{2}}n^{2-\frac{1}{s}}+\frac{1}{2}(s-1)n=O(n^{1-\frac{1}{s}})

**Remark 2.** Last definition is **BFS Tree Method**, which is systematic algorithm for exploring every node in a tree data structure level by level.

Homework

Problem 1.

Prove: Every $n$ -vertex graph with at least $2ex(n,C_4)$ edges contains at least $(\frac{3}{2}-o(1))n^2$ many copies of $C_4$ .

Proof.

Let $G$ be an $n$ -vertex graph with $m=e(G)\ge 2ex(n,C_4)$ . For distinct vertices $x,y$ , we note

N_{xy}:=|N(x)\cap N(y)|.

Define a labeled fork to be an ordered triple $(x,z,y)$ with $x\neq y$ and $xz,zy\in E(G)$ . Let $F$ be the number of labeled forks.

Counting by the center $z$ :

F=\sum_{z\in V(G)} d(z)(d(z)-1).

By Jensen Inequality,

F\ge n\left(\frac{2m}{n}\right)\left(\frac{2m}{n}-1\right)=\frac{4m^2}{n}-2m.

By Theorem 1, we get

m\ge 2ex(n,C_4)=(1+o(1))n^{3/2},

hence

F\ge (4-o(1))n^2.

Counting forks by endpoints:

F=\sum_{x\neq y} N_{xy}=2\sum_{\{x,y\}\in \binom{V}{2}} N_{xy},

\sum_{\{x,y\}} N_{xy}\ge (2-o(1))n^2.

Let $N=\binom{n}{2}=(\frac12+o(1))n^2$ . By convexity of $u\mapsto \binom{u}{2}$ ,

\sum_{\{x,y\}}\binom{N_{xy}}{2} \ge N\binom{\frac{1}{N}\sum_{\{x,y\}}N_{xy}}{2} \ge N\binom{4-o(1)}{2} =(3-o(1))n^2.

Now $\sum_{\{x,y\}}\binom{N_{xy}}{2}$ counts each $C_4$ exactly twice (once for each pair of opposite vertices). Therefore

\#C_4(G)\ge \frac12(3-o(1))n^2 =\left(\frac32-o(1)\right)n^2.

∎

Problem 2.

Prove: Every set of $n$ points in the Euclidean plane $\mathbb{R}^2$ has at most $O(n^{3/2})$ unit distances.

Proof.

Let $P$ be the $n$ -point set, and build a graph $G$ on vertex set $P$ by joining two points iff their Euclidean distance is $1$ . Then $e(G)$ is exactly the number of unit distances.

Hence $e(G)\le ex(n,K_{2,3})$ . By Theorem 2,

ex(n,K_{2,3})\le (3-1)^{1/2}n^{3/2}+(2-1)n=\sqrt{2}\,n^{3/2}+n=O(n^{3/2}).

Therefore the number of unit distances is $O(n^{3/2})$ .

∎

Problem 3.

Prove: For fixed $k\ge 2$ , there exists a constant $c_k$ such that

ex\!\left(n,\mathcal{C}_{\le 2k}^{e}\right)\le c_k n^{1+1/k}, \qquad \mathcal{C}_{\le 2k}^{e}=\{C_4,C_6,\dots,C_{2k}\}.

Proof.

Let $G$ be an $n$ -vertex graph with no even cycle of length at most $2k$ , and let $m=e(G)$ .

Let $n_H=|V(H)|\le n$ , and $d=2e(H)/n_H$ be the average degree of $H$ . By repeatedly deleting vertices of degree $<d/2$ , we get a nonempty subgraph $H'\subseteq H$ with minimum degree

\delta(H')\ge d/2.

Also girth $(H')>2k$ .

Pick $v\in V(H')$ and run BFS: levels $L_0=\{v\},L_1,\dots,L_k$ . Because girth is $>2k$ , the ball of radius $k$ is tree-like, hence

|L_1|\ge \delta,\qquad |L_i|\ge (\delta-1)|L_{i-1}| \ (2\le i\le k),

where $\delta=\delta(H')$ . Therefore

n\ge n_H\ge |V(H')| \ge 1+\delta\sum_{i=0}^{k-1}(\delta-1)^i \ge (\delta-1)^k.

So $\delta\le n^{1/k}+1$ , and thus

d\le 2\delta\le 2n^{1/k}+2.

Hence

e(H)=\frac{dn_H}{2}\le \frac{dn}{2}\le n^{1+1/k}+n.

Finally,

m\le 2e(H)\le 2n^{1+1/k}+2n\le 4n^{1+1/k}.

So we may take $c_k=4$ and has

ex\!\left(n,\mathcal{C}_{\le 2k}^{e}\right)\le c_k n^{1+1/k}.

∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 7

Search

Modern Graph Theory — Homework 7

Assignments: Apr 21st, 2026

Review

Homework

PDF

Assignments: Apr 21st, 2026

Review

Homework

PDF