Turan's Theorem

Lecture Notes for CS477 combinatorics on 2025/03/24

flipping a coin

p∈[0,1]p\in[0,1] 均匀随机，问100次恰有50次H的概率？

∫01(10050)p50(1−p)50dp=(10050)B(51,51)=1101\int_0^1{100\choose50}p^{50}(1-p)^{50}\text{d} p={100\choose50}B(51,51)=\frac{1}{101}

另外一种：

∫01(10050)p50(1−p)50dp=∑r=050(−1)r(10050)(50r)151+r=?1101\int_0^1{100\choose50}p^{50}(1-p)^{50}\text{d} p=\sum_{r=0}^{50}(-1)^r{100\choose50}{50\choose r}\frac{1}{51+r}=^?\frac{1}{101}

即证

∑r=050(−1)r101!50!50!50!r!(50−r)!151+r=∑r=050(−1)r(10151+r)(50+rr)=?1\sum_{r=0}^{50}(-1)^r\frac{101!}{50!50!}\frac{50!}{r!(50-r)!}\frac{1}{51+r}=\sum_{r=0}^{50}(-1)^r{101\choose 51+r}{50+r\choose r}=^?1

induced subgraph

GG 没有诱导子图是 P3P_3   ⟺  \iff GG 的每个连通块都是团.

左推右.

  1. 归纳法，在连通块中先挑一个，它对其他总有一条边，将相应的点加入；直到选到所有连通块中的点.

  2. 连通块中任意两点必有路径，因此每个 P3P_3 必须加边成三角形.

  3. 任何一个点，其邻居必定两两相邻. 因此 v∪N(v)v\cup N(v) 是一个团. 假设这连通块还有剩余的点，则 xx 到N(v)N(v) 中某点相邻，那么 xx 和 vv 相邻.

  4. 用等价关系来考虑，简单无向图——对称性，无 induced P3P_3 ——传递性，再加上所有自环即可，由于等价关系  ⟺  \iff 分划.

Turan 定理八股文

Thm. (Turan, 1941) n 阶图 ω≤p\omega\leq p, 那么 m≤t(n,p)m\leq t(n,p), t(n,p)t(n,p) 为完全 pp 部图 T(n,p)T(n,p) 的边数.

我们可估计 t(n,p)∼(1−1p)n22t(n,p)\sim (1-\frac{1}{p})\frac{n^2}{2}, 一种方法是直接计算，还有一种是看每一个点都被砍了 1/p1/p 条出边.

证1. (from the last proof of Mantel's Thm)

ρ=∑uv∈Ef(u)f(v)\rho=\sum_{uv\in E}f(u)f(v)

不断调整每一对不相邻的非零点对，最后0个数越来越多直到停下, 最后剩下的非零点两两相邻，那么剩下的点个数 =r≤p=r\leq p, 由 Cauchy m=ρ≤(1−1/r)n22≤(1−1/p)n22m=\rho\leq(1-1/r)\frac{n^2}{2}\leq(1-1/p)\frac{n^2}{2}.

证2. Induction. 若 n≤pn\leq p 自然成立 (KnK_n); n>pn>p 假设 GG 是 mm 最大的 nn 阶 ω≤p\omega\leq p 图. 有 ω(G)=p\omega(G)=p (否则，若 ω(G)<p\omega(G)\lt p, 随便加一条边，ω\omega 至多增加1). 挑出这个 KpK_p 和其他点，m≤(p2)+t(n−p,p)+(n−p)(p−1)m\leq{p\choose2}+t(n-p,p)+(n-p)(p-1).

我们用定义即可证明 m≤(p2)+t(n−p,p)+(n−p)(p−1)=t(n,p)m\leq{p\choose2}+t(n-p,p)+(n-p)(p-1)=t(n,p), 考虑 p 部图 T(n,p)T(n,p), 只有国际边，每个国挑出一个代表，提出来，这些代表是 p-团. 剩下的 n-p 个点，每个点都连了 p 个代表中的 p-1 个；剩下的图是 T(n−p,p)T(n-p,p), 因此等号成立.

证3. 设我们要的图是 GG, 即 GG 满足 n 阶，ω≤p\omega\leq p 且 m 最大. 往证 GG 是完全某部图.

完全 p 部图中，边数最大的就是 T(n,p)T(n,p). 因此如果能证上面的命题，就成功了. 为什么是“某”部图？考虑 T(5,8)T(5,8).

Lemma. (x,y)∉E⇒deg⁡x=deg⁡y(x,y)\notin E\Rightarrow \deg x=\deg y.

否则可以通过复制的方法增加边数. 若 deg⁡x<deg⁡y\deg x\lt \deg y, 考虑 G−x+y′G-x+y^\prime, 首先复制一个 yy 不会增加 ω\omega.

填空题，你可以填 “矛盾” 🤣🤣

call back 我们关于 induced P3P_3 的讨论. 如果不是完全某部图，那么其补图不是每个连通块都是团，因此存在 induced P3P_3. 因此应该填 原图存在 induced · | , 所以根据 Lemma 有 deg⁡u=deg⁡v=deg⁡w\deg u=\deg v=\deg w.

证4. (Erdos)

v 为度数最大的点，A=N(v),B=V∖N(v)A=N(v),B=V\setminus N(v)，AA 中没有 p-团. 先由归纳假设，将 AA 补成 T(∣A∣,p−1)T(|A|,p-1), BB 国内边全去掉, 然后将 A,BA,B 的点全部连起来形成 HH.

在 GG 中，由于 vv 的度数最大, ∑x∈BdxG≤∑x∈BdvG=∣A∣∣B∣\sum_{x\in B}d_x^G\leq \sum_{x\in B}d_v^G=|A||B|; 在 HH 中，∣A∣∣B∣=∑v∈BdvH|A||B|=\sum_{v\in B}d_v^H. 因此

mG=∑AA 边+∑BB 边+∑AB 边≤T(∣A∣,p−1)+2∑BB 边+∑AB 边=T(∣A∣,p−1)+∑x∈BdxG≤T(∣A∣,p−1)+∣A∣∣B∣=mH\begin{align} m_G&=\sum\text{AA 边}+\sum\text{BB 边}+\sum\text{AB 边}\nonumber\\ &\leq T(|A|,p-1)+2\sum\text{BB 边}+\sum\text{AB 边}\nonumber\\ &=T(|A|,p-1)+\sum_{x\in B}d_x^G\nonumber\\ &\leq T(|A|,p-1)+|A||B|\nonumber\\ &= m_H\nonumber \end{align}

由于 HH 是 完全 p-部图，我们有 mG≤mH≤t(n,p)m_G\leq m_H\leq t(n,p).

证5.

Lemma. 对任意图 GG, ∑v∈G1deg⁡v+1≤α\sum_{v\in G}\frac{1}{\deg v+1}\leq\alpha.

将 GG 中的点随机排在直线上，对于每个点来说，如果它的朋友都在它后面 (这件事有 1deg⁡v+1\frac{1}{\deg v+1} 的概率发生)，那么它😊，否则😒. E[#😊]=∑v∈G1deg⁡v+1\mathbb{E}[\#😊]=\sum_{v\in G}\frac{1}{\deg v+1}. 选出所有😊的点，它们一定构成独立集，因此 ∑v∈G1deg⁡v+1≤α(G)\sum_{v\in G}\frac{1}{\deg v+1}\leq\alpha(G)

我们考虑关于补图的 Turan: GG 满足 α≤p\alpha\leq p, 那么 m≥c(n,p)m\geq c(n,p).

反设 m<c(n,p)m\lt c(n,p)