[Graph Theory] Extremal Problems

10.1. The extremal numbers. 

graph 의 parameter 와 structure. 그래프에 관련된 수 (엣지, 노드 갯수)와 그래프의 구조를 연결시키는 그래프 이론.

예를 들면, n-vertex graph 의 엣지 갯수가 삼각형의 갯수를 어떻게 보장할까? 뭐 이런.

심플하게 생각하면, edge가 많을수록 삼각형도 많겠지. no triangle이 되게 하는 엣지의 최대 갯수는 몇 개일까? 이런 질문들이 가능.

Definition

extremal number, Turan number, $ex(n, F)$: n짜리 그래프가 $F$ 를 subgraph로 갖지 않는 최대의 엣지 갯수. 엣지는 최대한 그리는데, F는 없게.

Turan graph, $T_r(n)$: balanced complete r-partite graph with n vertices. n개짜리 그래프인데, 완전 r-partite.

$t_r(n)$: $T_r(n)$ 의 엣지 갯수.

 

그러니까 Turan number 는 $F$ 를 안갖게 하는 edge 갯수를 말하고, 

Turan graph 는 r-partite graph 를 말한다.

 

Theorem <Turan's theorem>

$K_{r+1}-free$ n-vertex graph 는 최대 $t_r(n)$개의 edge를 가지고, 최대일 때에는 $T_r(n)$일 때가 유일하다.

$r+1$ 짜리 clique 가 없는데 엣지는 많고 싶어? 그럼 r-partite graph 가 되면 되지~

 

Theorem <Caro, Wei>

$n, r \in \mathbb{N}$ 이고, $n \geq r$ 이고 $n = qr+k$ 라고 치자. $0 \geq k < r$ 이고.

n짜리 vertex graph $G$, $e(G) < k \binom{q+1}{2} + (r-k)\binom{q}{2}$ 는 $\alpha(G) \geq r+1$ 이다.

edge 갯수가 일정 갯수보다 낮아야 r 개의 partite 보다 independent set size 가 더 크다.

$\textit{Proof}$

ordering $\sigma = (v_1, ..., v_n)$ 을 생각해봐. 각 ordering 의 확률은 $n!^{-1}$.

어떤 $U(\sigma)$ 라는 set을 골라봐. 모든 vertices 가 그들의 neighbor보다 앞에 있는 ordering 이야.

이러면 $U(\sigma)$ 가 $G$의 independent set이야.

$X(\sigma) = |U(\sigma)|$, 그러니까 저 size 가 rv라고 했을 때, $X = \sum_{v \in V(G)} I_v$ 이고,

$

I_v(\sigma) := 

\begin{cases}

1 & \textit{if } v \in U(\sigma) \\

0 & \textit{if } v \notin U(\sigma) \\

\end{cases}

$

그 ordering 은 uniformly random 하게 골라졌으니까, $v$가 모든 neighbors 앞에 나타날 확률은 $Pr[I_v = 1] = (d(v) + 1)^{-1}$ 이다. <왜? d(v) 개보다 v가 앞에 있을 확률이 이거지??>

$\mathbb{E}[X] = \sum_{v \in V(G)} \mathbb{E}[I_v] = \sum_{v \in V(G)} \frac{1}{d(v)+1}$

일단 $\sum_{v \in V(G)}(d(v)+1) = 2e(G) + n$ 이 고정되어 있으니까, $V(G)$ 의 degree 들이 even 할 때에 이게 최소가 된다. $2(k \binom{q+1}{2} + (r-k) \binom{q}{2}) + n > 2m+n$ 이니까,

$\mathbb{E}[X] > (r-k) q \cdot \frac{1}{q} + k(q+1) \cdot \frac{1}{q+1} = r$ 이다.

이게 $|U(\sigma)| \geq r+1$ 인 $\sigma$가 존재함을 얘기하는 거니까, r+1 이상의 indep. set을 가진다.

 

에 그러니까, r짜리 partite 가 q개 있고, 거기에 포함 안된 녀석들이 k개 있는 형국이라고 치자.

그럼 edge 갯수는 balanced 하게 엮여있는 q+1개 짜리 size 의 k개 그룹을 잇는, 그리고 q개가  clique를 이루고 있는 r-k 개의 edge들을 합쳐서 그것보다 적은 경우에, 

우리는 vertex ordering 으로 나타날 수 있는 set의 확률의 기댓값을 구해서 indep. set 의 기댓값이 r개보다 많다는 걸 보여줌으로 얻을 수 있다는 뜻.

 

Proposition 10.4

$n, r \in \mathbb{N}$ 이고, $n \geq r$ 이고 $n = qr+k$ 라고 치자. $0 \geq k < r$ 이고.

n짜리 vertex graph $G$, $e(G) = k \binom{q+1}{2} + (r-k)\binom{q}{2}$ 는 $\alpha(G) = r$ 이다.

그리고 $G$는 disjoint union $kK_{q+1} \cup (r-k) K_q$ 이다.

$\textit{Proof}$

$\mathbb{E}[X] = \sum_{v \in V(G)} \mathbb{E}[I_v] = \sum_{v \in V(G)} \frac{1}{d(v)+1} \geq r$

까지는 나왔다. 그런데 $G$에는 r+1 짜리 size의 indep. set이 없다, 그러니까 $\mathbb{E}[X] = r$ 이다. 위 식에서 봤을 때 $d(v)$는 최대한 지들끼리 가까워야 하고, $X$ 는 constant RV여야 한다.

$G$ 가 union of cliques 가 아니라고 가정하면, ordering 이 여러개가 되면서 $X=|U(\sigma)|$ 의 가정에 모순이 생기므로, $G$는 union of clique가 맞다. $G$의 degree가 최대한 even 해야 하므로, proposition 증명 성공.

 

Theorem 10.5 <Erdos-Stone, Erdos-Simonovits>

$F$ 가 $\chi(F) = r+1$ 인 그래프라고 하자. $\delta > 0$ 이고, $n_0 \in \mathbb{N}$이 존재한다면, 모든 $n \geq n_0$에 대해 아래가 성립

$ex(n, F) \leq (1- \frac{1}{r} + \delta) \frac{n^2}{2}$.

이게 뭘 의미하냐면, $\lim_{n \rightarrow \infty} \frac{ex(n, F)}{\binom{n}{2}} = 1 - \frac{1}{r}$ 을 의미.

 

Claim 3.

$r, h \in \mathbb{N} \cup \{0\}$ 이랑 $\delta > 0$ 일 때, $n > n_1$ 에 대해 $n_1 = n_1(r, h, \delta)$ 가를 만족한다

$G'$ 이 n-vertex graph with $\delta(G') \geq (1 - \frac{1}{r} + \delta/2)n$ 일 때, $G'$ 가 complete (r+1) partite graph 를 포함한다면, 최소 $h$ 사이즈의 각 파트를 subgraph 로 가진다.

 

뭔소리야

어쨌거나, r+1 complete graph 를 피하고 싶으시면, 애들을 일단 r개의 그룹으로 나누면 그룹끼리 아무리 degree를 그려봤자 절대 r+1 complete graph 가 안나온다는 의미입니다.

 

10.2. Degenerate extremal numbers

bipartite graph 는 extremal problem 의 degenerate clases 다.

 

Theorem <Kovari-Sos-Turan>

$s, t \in \mathbb{N}$ 이고 $s \leq t$일 때,

$ex(n, K_{s, t}) \leq tn^{2-1/s}$

$\textit{Proof}$

$G$ 가 n-vertex graph 이고, 최소 $tn^{2-1/s}$ edge 를 가진다고 치자. $V = V(G)$야.

$\sum_{v \in V} |\binom{N(v)}{s}| = \sum_{v \in V} \binom{d(v)}{s} \geq n \binom{\frac{1}{n}d(v)}{s} \geq n \binom{2tn^{1-1/s}}{s} \geq \frac{(tn)^s}{s!} \geq t \binom{n}{s}$

 

 뭔소리야, 일단 여기서 pigeonhole 때문에 최소 $t$개의 distinct vertices 를 갖는 $N(v)$ 가 포함되는 size $s$ 짜리 set $S$ 가 나오긴 한대...

 

Theorem

$s \geq 2$ 라고 하자, holds for all $n \geq n_0$, 

$e(G) \geq \frac{1}{5}n^{2-2/(s+1)} 이고 $K_{s, s}$ 를 갖지 않는 n-vertex가 존재한다.

$\textit{Proof}$

edge 의 확률이 $p = n^{-n/(s+1)}$ 이라고 치자, fixed pari $(A, B)$ 라고 헀을 때 $|A| = |B| = s$ 일 때, (A, B) 가 complete bipartite graph 가 될 확률이 $p^{s^2}$. 

$X$ 가 number of edge 고 $Y$ 가 $K_{s, s}$ 의 갯수라고 했을 때, linearity of expectation 으로

$\mathbb{E}[X-Y] = p \binom{n}{2} - \sum_{A, B \in \binom{[n]}{s}, A \cap B = \emptyset} p^{s^2} \geq \frac{1}{2}n^{2s/(s+1)} - \frac{1}{2} \binom{n}{s} \binom{n-s}{s} p^{s^2} \geq \frac{1}{2} n^{2s/(s+1)} - \frac{n^{2s}p^{s^2}}{2s!^2} \geq \frac{1}{5}n^{2s/(s+1)}

 

Theorem

n 개의 vertex 와 $(\frac{1}{2} - o(1))n^&{3/2}$ 개의 edge를 가지면서 $C_4$는 안가지는 그래프가 존재한다.

 

10.3. Counting triangles

앞에서 다뤘던 건, edge가 몇 개 넘어가야 $F$가 생기니? 였지.

그런데 사실 $F$ 몇개있니? 가 더 궁금할 거라고. 가장 쉬운 $K_3$, triangle 부터 시작해보자.

 

Theorem <Moon-Moser>

$G$ with $n$ vertices and $m$ edge 들은 최소 $\frac{m}{3n}(4m-n^2)$ 개의 triangle 을 가진다.

 

Definition

$k_r(G)$: r-clique의 갯수

 

Ramsey theorem 으로 예를 들면, $k_3(G) + k_3(\overline{G}) > 0$ 이라는 거지.

 

Lemma

$G$ 가 n 개의 vertex, m개의 엣지를 가진다면

(1) $k_3(G) + k_3(\overline{G}) = \binom{n}{3} - \frac{1}{2}\sum_v d(v) (n-1-d(v))$

(2) $k_3(G) + k_3(\overline{G}) = \binom{n}{3} - (n-2)m + \sum_v \binom{d(v)}{2}$

$\textit{Proof}$

예를 들어서 우리가 $E(K_n)$ , complete graph 의 edge를 색칠한다고 치고, first color 로 칠해진 애들로 monochromatic triangle 을 센다고 치자.

incident edge끼리 같은 color를 가지면 weight 를 2, 그렇지 않으면 -1을 주면

깔끔하게 세 개의 색이 모두 같아야지만 6이 나오는 counting weight를 가지게 된다.

모든 incident edge 의 pair 의 weight 합은 $6(k_3(G) + k_3(\overline{G})$ 라는 것.

각 $v$에 대해서, the sum of the weight 은

$2 \binom{d(v)}{2} + 2\binom{n-1-d(v)}{2}-d(v)(n-1-d(v))$

그리고 $\binom{y}{2} + \binom{x-y}{2} = \binom{x}{2} - y(x-y)$ 니까, $v = 2\binom{n-1}{2} - 2d(v)(n-1-d(v))$ 라고 할 수 있다. 모든 걸 6으로 나누면 (1)식이 나오고, $n-1$ 을 $n-2+1$로 바꾸고 ahdnshake lemma 를 쓰면 (2)가 나온다.

 

Theorem <Goodman>

n짜리 graph 와 이것의 complement 는, 최소 $n(n-1)(n-5)/24$개의 triangle을 가지고, $n \equiv 1 pmod{4}$ 일때 sharp 한 bound이다.