Interactive Geometric Ramsey Theory Workbench

Prerequisites Explored, Full Proofs, and Interactive Simulations for Larman et al. (1994)

1. Prerequisites Explained

To tackle papers like Larman et al. (1994), you need three core mathematical building blocks. Here is what they actually mean in plain English:

  • Dilworth's Theorem: Imagine you have a messy pile of items that can be partially compared (a poset). Dilworth's theorem states you can always break that pile into either a neat sequential line (a chain) of length p, or a wide cluster of items that cannot be compared to each other (an antichain) of size at least n/p. In Theorem 1, the authors use this to filter disjoint shapes.
  • Intersection Graphs: A way of translating geometry into network science. Each geometric shape becomes a "vertex" (dot), and you draw an "edge" (line) between two vertices if their corresponding shapes overlap in physical space. Complete subgraphs mean all shapes overlap (pairwise intersecting), while empty subgraphs mean no shapes touch (pairwise disjoint).
  • Sweep-Line Algorithms: A computational geometry technique where you imagine sweeping a vertical line across the plane from left to right. As the line moves, it pauses when it hits key structural features (like the edge of a rectangle), allowing you to analyze active objects locally. This powers the induction proof in Theorem 2.

2. Interactive Workbench: The 4-Relation Sieve Simulator

Test how the lower-bound sieve works. Click the button to run shapes through the four directional binary relations (Relation 1 through 4) to see how the pool filters down to a guaranteed uniform group.

Live Simulation: Filtering n Shapes

Initial State: 1000 random convex shapes loaded.

Remaining Pool: 1000
Current Filter: None
Guaranteed Group: None

3. Theorem 1: General Convex Sets & The 4-Relation Sieve

The lower bound f(n) >= n^0.2 is achieved by sequentially filtering disjoint pairs through four distinct transitive binary relations based on their projections onto the X-axis.

x-axis n(A) A n(B) B Overlap
Visualizing X-projections n(A), n(B) and vertical stacking for relations 1 through 4.
View Full Proof Details: The Four Relations & Dilworth Sieve

For any two disjoint convex sets A and B, the authors define:

  • Relation 1: n(A) is subset of n(B) and A is below B.
  • Relation 2: n(A) is subset of n(B) and A is above B.
  • Relation 3: Left/right endpoints staggered, and in the overlap region, A is above B.
  • Relation 4: Left/right endpoints staggered, and in the overlap region, A is below B.

By Dilworth’s Lemma, applying this 4-step sieve forces either a chain of size n^(1/5) (disjoint sets) or leaves an antichain of size n^(1/5) where every pair intersects because they are incomparable in all 4 relations.

4. Construction 2.4: The 5-Cycle Fractal Trap

To prove the upper bound f(n) <= n^(log 2 / log 5) approx n^0.431, the authors construct a recursive geometric gadget based on a 5-cycle intersection graph.

p1q1 p2q2 p3q3
The 5-segment gadget where each segment intersects only its two adjacent neighbors.
View Full Proof Details: Recursive Fractal Explosion

Start with 5 segments forming a 5-cycle graph. Each segment p_i q_i intersects only p_(i-1)q_(i-1) and p_(i+1)q_(i+1). To scale up to step k, replace each segment with a miniature copy of the 5-segment gadget scaled down by a tiny epsilon > 0.

The total number of segments grows as n = 5^k, while the maximum independent or complete subgraph size grows as 2^k. Solving for the exponent yields:

log 2 / log 5 approx 0.43067

5. Theorem 2: Axis-Parallel Rectangles & Sweep-Line Induction

When shapes are restricted to axis-parallel rectangles, the bound jumps dramatically to n / (2 log n) because rectangles cannot wrap around each other like line segments.

Sweep Line v
Inductive split using the right vertical side of the t-th rectangle as a sweep-line cut.
View Full Proof Details: Mathematical Induction

Let psi(m) be the minimum n such that D(F)I(F) >= m for axis-parallel rectangles. The authors prove by induction that psi(2^k) <= k * 2^k.

The Induction Step: For a family of k * 2^k rectangles, choose vertical line v at the t-th rightmost vertical side. Either >= 2^k rectangles cross v (yielding an interval-intersection reduction), or they split into left and right subfamilies, each satisfying the inductive hypothesis.