Crossing Lemma

Lecture Notes for CS477 combinatorics on 2025/05/19

Crossing number

平面图 m≥3n−6m\geq 3n-6

规定不能三边交叉于一点，GG 的 crossing number 定义为最小交叉数量，例如 K5K_5 至少一个，Cr(K5)=1\text{Cr}(K_5)=1.

Thm. Cr(G)≥m−3n\text{Cr}(G)\geq m-3n

证1. 交点变成点，点+1，边+2，得到平面图 证2. 一个交点去一条边，至少少一个交点，因此至多去掉 Cr\text{Cr} 条边

Somehow when m≥4n,  Cr≥364(n4)(m(n2))3m\geq 4n, \;\text{Cr}\geq\frac{3}{64}{n\choose 4}\Big(\frac{m}{n\choose 2}\Big)^3

Thm. (1980, Crossing Lemma) Cr(G)≥m364n2(m≥4n)\text{Cr}(G)\geq\frac{m^3}{64n^2}(m\geq 4n)

Cr(Kn)\text{Cr}(K_n): 每5个点有1个交点；每个交点被算 n−4n-4 次

归纳法 W⊆V,H=G[W],X(H)=n,Y(H)=m,Z(H)=(H在G的最优画法下的交点个数)W\subseteq V,H=G[W],X(H)=n,Y(H)=m,Z(H)=(H\text{在}G\text{的最优画法下的交点个数}) 有 Z≥Cr≥Y−3XZ\geq \text{Cr}\geq Y-3X. 将 VV 中的点以概率 pp 选入 WW, 算期望 p4Cr(G)≥p2m−3pnp^4\text{Cr}(G)\geq p^2m-3pn, 取 p=4nm≤1p=\frac{4n}{m}\leq1 即可

crossing lemma 应用: 好边

Thm. (Szemeredi-Trotter) nn points ∈R2\in\mathbb{R}^2, 定义一条直线为好边当且仅当线上有 ≥k  (2≤k≤n)\geq k\;(2\leq k\leq \sqrt{n}) 个点. 这样的好边最多 O(n2k3)O\big(\frac{n^2}{k^3}\big) 个.

将好线上的相邻点 (consecutive) 连边，点数 nn, 边数 ≥l(k−1)\geq l(k-1), 交叉数 ≤(l2)\leq{l\choose 2}. 比较 mm 和 4n4n 大小.

已知 k≤nk\leq \sqrt{n}, m<4n⇒l<4nk−1≤O(n2k3)m\lt 4n\Rightarrow l\lt \frac{4n}{k-1}\leq O\big(\frac{n^2}{k^3}\big)

m≥4n⇒m\geq 4n\Rightarrow crossing lemma l22≥l3(k−1)364n2\frac{l^2}{2}\geq\frac{l^3(k-1)^3}{64n^2}

这个界是紧的. 假设有均匀点阵 k×nkk\times\frac{n}{k}, 最上面的一个点出发，有 nk2\frac{n}{k^2} 条好边. 因此总共有 n2k3\frac{n^2}{k^3} 条

cl 应用：number of incidences

I(P,L)={(p,l):p∈P,l∈L,p∈l}I(P,L)=\{(p,l):p\in P,l\in L,p\in l\}

Thm. (Szemeredi-Trotter) ∣P∣=n,∣L∣=m,∣I(P,L)∣≤4(m23n23+m+n)|P|=n,|L|=m,|I(P,L)|\leq 4(m^{\frac{2}{3}}n^{\frac{2}{3}}+m+n)

连接线上的相邻点，不放假设每条边至少1个点（否则直接删除，mm 减少，不影响待证不等式）。点数 nn, 边数：每条线如果有 n>1n>1 个点，那么有 n−1n-1 条边，共 ∣I∣−m|I|-m 条. 交点最多 (m2){m\choose 2}

crossing lemma: 要么 ∣I∣−m<4n|I|-m\lt 4n, 要么 m22≥Cr≥(∣I∣−m)364n2\frac{m^2}{2}\geq\text{Cr}\geq\frac{(|I|-m)^3}{64n^2}

cl 应用：decent graph 最大边数

erdos：不存在 K2,3K_{2,3}，因此 m<n1.5m\lt n^{1.5}

考虑每个点为中心画单位圆，圆上的相邻点连边得到图 H. 需保证无重边、自边

  1. deg⁡(v)<3\deg(v)\lt 3 直接去掉，-2n
  2. 两点都是公共邻居 直接去掉，/2

得到 mH=∑deg⁡(v)−2n2=mG−nm_H=\frac{\sum\deg(v)-2n}{2}=m_G-n, 应用 crossing lemma, 交点最多是每两个圆交两个，因此 mH364nH2≤Cr(H)≤n2\frac{m_H^3}{64n_H^2}\leq \text{Cr}(H)\leq n^2，mG≤O(n43)m_G\leq O(n^{\frac{4}{3}})

cl 应用：distinct distances

平面上 nn 个点，至少距离种类数

可用 Erdos-Szekeres 定理说明这个种类数量为 Ω(n)\Omega(\sqrt{n}): 从左到右看，一定存在递增 n−1\sqrt{n-1} 或递减的 n−1\sqrt{n-1} 个点。无论递增递减，从第一个点看，距离至少一定是越来越大的，因此至少 n−1−1\sqrt{n-1}-1 个距离.

但是以两点为圆心，往外画 O(n)O(\sqrt{n}) 个圆形，最多 O(n)O(n) 个交点，因此这个数量严格大于 O(n)O(\sqrt{n}); 由于每种距离最多 O(n43)O(n^{\frac{4}{3}}) (上面证过了)，可证至少 O(n23)O(n^{\frac{2}{3}}) 种距离

下证 O(n0.8)O(n^{0.8})

引入重边图 kGkG 表示每条边都重复 kk 遍. Cr(kG)=k2Cr(G)\text{Cr}(kG)= k^2\text{Cr}(G)

GG 有重边，重数 ≤k\leq k, m≥20knm\geq 20kn, 则 Cr(G)≥O(m3kn2)\text{Cr}(G)\geq O(\frac{m^3}{kn^2})

如果 kk 全部满，那么上面的 bound 可以取到；然而如果不满，这个界不够强（为什么？）

对任意的图 GG, 第一阶段，每个边以 1/k 概率选取；第二阶段，每个重复的只选一个. 每条边留下来的概率\lt =1/k

Z是这个画法的crossing E[Z]≤Cr/k2\mathbb{E}[Z]\leq Cr/k^2 每条边活过两个阶段的概率\lt 1/k. Y为边数，每一条边，如果第一阶段唯一的活下来，就成功，因此有留下概率下界 mk(1−1k)k−1≤E[Y]≤mk\frac{m}{k}(1-\frac{1}{k})^{k-1}\leq E[Y]\leq \frac{m}{k}

either m≤4nm\leq4n, or Cr≥m3/(64n2)Cr\geq m^3/(64n^2), 因此综合起来，Cr(G)≥m364n2−n\text{Cr}(G)\geq\frac{m^3}{64n^2}-n

Z≥Y364n2−nZ\geq\frac{Y^3}{64n^2}-n 期望+jensen不等式 Crk2≥(m3k)364n2\frac{\text{Cr}}{k^2}\geq \frac{(\frac{m}{3k})^3}{64n^2}

(to be continued.)