AI summary by TwinMind
Crossing Number Inequality
MIT OpenCourseWare
18m 26s
Introduction to Crossing Number
- Crossing number = minimum number of edge crossings in any planar drawing of graph G
- Some graphs drawable without crossings (planar graphs)
- Example: K4 (complete graph on 4 vertices) is planar
- Some graphs require crossings
- Example: K5 (complete graph on 5 vertices) requires minimum 1 crossing
- Question: Do graphs with many edges necessarily have high crossing numbers?
Crossing Number Inequality Theorem Statement
- For graph G with vertex set V and edge set E
- If |E| ≥ 4|V|, then crossing number of G ≥ C|E|³/|V|²
- C is some absolute constant
- Corollary: If |E| = Ω(|V|²), then crossing number = Ω(|V|⁴)
- Upper bound: at most (E choose 2) crossings possible
Proof Step 1: Analysis of Planar Graphs
- If G is planar (crossing number = 0), then |E| ≤ 3|V|
- Equivalently: average degree ≤ 6
- Proof uses Euler's formula from topology
- V - E + F = 2 (vertices - edges + faces = 2)
- Example verification: 4 vertices, 5 edges, 3 faces → 4-5+3=2
Proof Step 2: From One Crossing to Many
- Given non-planar graph G
- Delete crossing number of G edges to make it planar
- Apply Step 1 bound to resulting planar graph
- |E| - crossing_number(G) ≤ 3|V|
- Rearranging: crossing_number(G) ≥ |E| - 3|V|
- Valid but weak bound (only linear improvement)
Proof Step 3: Probabilistic Bootstrapping
- Choose parameter p ∈ (0,1) to be determined
- Create random subgraph G' by keeping each vertex with probability p independently
- Delete vertices not chosen and all adjacent edges
- G' has vertex set V' and edge set E'
Expected Values Analysis
- E[|V'|] = p|V| (each vertex kept with probability p)
- E[|E'|] = p²|E| (edge kept if both endpoints kept, probability p²)
- E[crossing_number(G')] ≤ p⁴ × crossing_number(G)
- Each crossing kept if all 4 endpoints of crossing edges remain
- Uses same drawing as G (could potentially be improved)
Inequality Derivation
- Apply Step 2 bound to G': crossing_number(G') ≥ |E'| - 3|V'|
- Taking expectations: E[crossing_number(G')] ≥ E[|E'|] - 3E[|V'|]
- Substituting: p⁴ × crossing_number(G) ≥ p²|E| - 3p|V|
- Rearranging: crossing_number(G) ≥ (p²|E| - 3p|V|)/p⁴
Optimization
- Set p = 4|V|/|E| (valid since |E| ≥ 4|V| from theorem hypothesis)
- Ensures 0 < p ≤ 1
- Substituting optimal p:
- crossing_number(G) ≥ (1/64) × |E|³/|V|²
- Constant C = 1/64
Proof Summary and Method
- Step 1: Analyze planar graphs using Euler's formula
- Step 2: Convert planar bound to weak crossing bound
- Step 3: Probabilistic bootstrapping strengthens weak bound
- Sample smaller subgraph randomly
- Apply weak bound to subgraph
- Optimization over sampling probability yields strong bound
- Demonstrates power of probabilistic method in combinatorics
