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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome