Extremal Graph

Definition (Graph Copy)

We say a Graph $G$ has a copy of another graph $F$ if $G$ has a subgraph that is isomorphic to $F$.

Definition (Turan Numbers)

Define

$$\text{ex}(n,F)$$

as the greatest number of edges that a graph on $n$ vertices that does not have a copy of $F$ can have.

Examples

Consider $\text{ex}(n,K_{1,2})$. Then we cannot have any copies like

graph LR;
	a((a)) o--o b((b));
	b o--o c((c));

which means we cannot have vertices of Degree more than $1$. Otherwise, we would get a copy of the Complete Graph $K_{1,2}$. This tell us our graph is a collection of disjoint $K_2$s and maybe $K_1$s. In particular, we only care about the edges, so at most we can have $\lfloor n/2\rfloor$.

More generally, for $K_{1,r}$, then $G$ must have maximum degree $\Delta (G)<r$. By the Handshake Lemma, then the number of edges $|E|\le \frac{n(r-1)}{2}$. Furthermore, if this is not an integer, then

$$|E|=\min \left(\left(\genfrac{}{}{0ex}{}{n}{2}\right),\lfloor \frac{n(r-1)}{2}\rfloor \right)$$

Let $F$ be the following graph

graph TD;
	a((a)) o--o b((b));
	c((c)) o--o d((d))

Then

$$\text{ex}(n,F)=\{\begin{array}{ll}n-1& n\ge 4\\ \left(\genfrac{}{}{0ex}{}{n}{2}\right)& \text{otherwise}\end{array}$$

Extremal Triangles

Likewise $\text{ex}(n,K_3)=\lfloor n^2/4\rfloor$. The way to look at it is to consider the maximal (in terms of edges) graph with no $K_3$. Consider $v$ where $\mathrm{deg}(v)=\Delta (G)$ and a non-adjacent vertex $w$. Potentially, $N(v)\cap N(w)\ne \varnothing$. We can replace $u\in N(w)$ with $u^{\prime }\in N(v)$.

We claim this creates no triangles and it can only increase the number of edges. If this edit creates a new triangle, then we have:

graph LR;
	w((w)) o--o x((x));
	x o--o y((y));
	y o--o w;

Since $w\notin N(v)$, then $x,y\ne v$. But then as $x,y\in N(w)$, then by construction, $x,y\in N(v)$. This implies that we have another triangle,

graph LR;
	v((v)) o--o x((x));
	x o--o y((y));
	y o--o v;

which is a contradiction on the assumption $G$ does not have any triangles. Then $|E|$ gained $|N(v)|$ and lost $|N(w)|$ edges. But as $v$ was maximal, then

$$|N(v)|-|N(w)|\ge 0$$

creating more edges.

What if we continued this on every non-adjacent $w$? Then every non neighbor of $v$ connects to every neighbor of $v$.

graph LR;
	v((v)) o--o Nv[[Nv]];
	v o--o Nv;
	v o--o Nv;
	v o--o Nv;
	Nv o--o a((1));
	Nv o--o a;
	Nv o--o a;
	Nv o--o b((2));
	Nv o--o b;
	Nv o--o c((...));

but this is a complete Bipartite Graph. But no matter graph we start with, we can always turn it to a bipartite graph. So if vertices $\{1,2,\dots \}$ are $k$ and $|N(v)|=n-k$, then

$$|E|\le |E(K_{k,n-k})|=k(n-k)=\{\begin{array}{ll}\frac{n^2}{4}& n\text{ is even}\\ \frac{(n+1)(n-1)}{4}& n\text{ is odd}\end{array}$$

but to maximize this, $k$ and $n-k$ must be as close as possible. If even, then $k=n/2$, and odd, then $k=n+1$ (or $n-1$).

Extremal Completes

What about $\text{ex}(n,K_r)$? Let $r>3$. If $r=2$ we cannot have edges and it is $0$. The complete bipartite graph example is quite good. We have $n^2/4$ edges over at most $n^2/2$. One way to show we have no triangles is to show a left and right part. Indeed, for any three vertices, by Pidgeonhole, at least $2$ vertices must be in the same part, and thus those two cannot be connected.

To generalize this, consider a $(r-1)$-partite graph, where the vertices are grouped into $(r-1)$ parts and there are edges between every pair of vertices in different parts but none in the same part.

Given this graph, we do not have a $K_r$ in it. For any $r$ vertices, by the Pidgeonhole Principle, at least two are in the same part, but these cannot have an edge. Thus we cannot have $K_r$.

Each part should generally have as close to equal as possible^[1]. In particular, the part size you need is either

$$\lfloor \frac{n}{r-1}\rfloor \text{ or }\lceil \frac{n}{r-1}\rceil$$

This leads to Turan’s Theorem.

Bipartite Dichotomy

If $H$ is not bipartite, then $\text{ex}(n,H)$ will be on the order of $n^2$.

Proof:

By theorem, if $H$ is not bipartite, then there is an odd cycle. However, we can construct complete bipartite $K_{n/2,n/2}$ which has $n^2/4$ edges. Thus $\text{ex}(n,H)\ge n^2/4$.

---

If $H$ is bipartite, then $K_{n/2,n/2}$ is no longer valid. This means we’ll need to drop some edges. In particular, instead of $n^2$, we have $n^{2-\epsilon }$ edges (sub quadratic).