Combinatorics course note - Turan problem

update: fix exercise ex2

课程链接 Course Link

闲来无事听的课，看看自己能坚持多久

习题解答并不能保证正确性

Turan Problem

就是求解一个数 extremal number of a graph H \[ ex(n,H)=max\{e(G) : |G|=n \, and \, G \;is \; H-free\} \] 在顶点数量限制下，不包含子图H，最大化边的数量

第一个结果是triangle-free的extremal number (Mantel 1907) \[ e(G)\le ex(n,K_3)= \left \lfloor n^2/4 \right \rfloor \] 最大的图是两边各有 \(\left \lfloor n/2 \right \rfloor\) 个点的二分图

exercise

• ex1: 选择n个无理数，怎么才能\(max\{\#(x_i,x_j):x_i+x_j \in Q\}\)
  • A：转化成图的问题，两个数和如果是有理数那么就有一条边，否则没有。注意到图中不能有三角形，那么根据上面的定理就解决了。
• ex2: 证明对于任意一个k个顶点的树 T, \(ex(n,T)\le kn\)
  • A: 如果图G有\(kn\)个边，那么一定能够找到它的一个子图G'，其最小度数大于等于k。简证：从G出发一步步删点，注意到开始时平均度数等于2k。若在某一步中得到图\(G^\prime\)，图中有一个点v度数小于k，那么把他去掉，得到的平均度数为 \[ \frac{\sum_{u\in G^\prime} d_{G^\prime}(u)-2d_{G^\prime}(v)}{|G^\prime|-1}\gt \frac{\sum_{u\in G^\prime} d_{G^\prime}(u)}{|G^\prime|} = \frac{2e(G^\prime)}{|G^\prime|}\ge 2k\] 这个平均值在一直增加，故最终一定可以得到所需的子图
  • T 可以表示成一个序列\([v_1,v_2,\dots,v_k]\) ，对每个\(v_i\) ，只有唯一个点\(v_j \in [v_1,\dots,v_{i-1}]\) ，\(v_i\)和\(v_j\)相连。由此可以构造性的证明，上述得到的子图G'包含所有k顶点的树。

  extremal structure

turan

r-partite turan graph => \(T_r(n)\) \[ ex(n,K_{r+1})=e(T_r(n))=(1-\frac{1}{r})\frac{n^2}{2}-O(r), \quad r\in N,r\ge2 \]

stability

let \(\epsilon > 0\), exists \(\delta > 0\), G be an n-vertex \(K_{k+1}\) -free graph, if \[ e(G)\ge ex(n,K_{r+1})-\delta n^2 \] then G can be changed to \(T_r(n)\) by altering at most \(\epsilon n^2\) adjacencies

Motzkin-Straus

\[ f_G(x)=x^TA_Gx=\sum_{v_iv_j\in e(G)}x_ix_j \]

\(\boldsymbol{x}\) in \(S_n\)， 其中 \(S_n\) 是概率单纯形。

\(\boldsymbol{x}\) 是n维的，所以可以看作是\(V(G)\)上的一个权重。

有\(f_G(\boldsymbol{x})=2e(G_x)\) , \(e(G_x)\) 是加权边的和，权重是两个顶点权重的乘积

定理内容：

图G，\(cl(G)=k\)，那么对于任意一个 \(\boldsymbol{x}\) in \(S_n\) 都有一个\(\boldsymbol{y}\in S_n\)， \[ \left\{\begin{matrix} f_G(y)\ge f_G(x)\\ supp(y)=K_k \end{matrix}\right. \] 进一步可知，\(f_G(\boldsymbol{x})\le \frac{k-1}{k}\)

实质上是给了一个最优化问题的解

证明略

exercise

• ex3: 证明 n个顶点的图\(G\)，两个子图\(G_1,G_2\) ，任取\(\boldsymbol{x}\) in \(S_n\)， 存在\(\boldsymbol{y}\in S_n\)，满足1. \(f_{G_i}(\boldsymbol{y})\ge f_{G_i}(\boldsymbol{x})\) ，2. \(\alpha(G[supp(\boldsymbol{y})])\le 2\) , (max independent number)
  • A: 只有个大概思路，没有具体去做。假设有三个点independent，鸽巢原理，至少有两个点属于一个子图，不妨设为\(G_1\)，做类似上述定理的证明，证明中所构造的\(\boldsymbol{y'}\) 恰好同样满足在\(G_2\)中的不等式。
• ex4: 证明一个有关一类图的邻接矩阵特征值的界。图G，\(cl(G)=k\) ，\(A_G\)邻接矩阵，有 \(\lambda_1(A_G)^2\le \frac{k-1}{k}\left \| A \right \|_F^2\)，\(\lambda_1\ge \lambda_2\ge \dots\)
  • A: 设 \(\lambda_1\) 的特征向量为 \(\boldsymbol{y}\; ,\left \| \boldsymbol{y} \right \|=1\) ，注意：\(\sum_{i=1}^n y_i^2=1\)，\(\left \| A \right \|_F^2=2e(G)\),
  • \(\lambda_1^2=f_{G_A}^2(\boldsymbol{y})=(\sum y_iy_j)^2\le 2e\sum y_i^2y_j^2\le \frac{k-1}{k}\left \| A \right \|_F^2\)

Erdos-Simonovits-Stone

\(\forall H\) \[ ex(n,H)=\left ( 1-\frac{1}{\chi(H)-1}+o(1) \right )\frac{n^2}{2} \]