This column is also available in pdf: filename RamseyLineSegment.pdf

Consider n line segments S₁,…,S_n on the plane in general position (ie., segments are either disjoint or intersect in exactly one point). We ask the following question:
How many pairwise disjoint segments OR how many pairwise intersecting segments are there?

Define the intersection graph G = (V,E) where each segment S_i is associated to a corresponding node V _i, and where there is an edge {V _i,V _j} if and only if the corresponding line segments intersect (S_i ∩ S_j ⁄= ∅). A subset of pairwise intersecting segments corresponds to a clique in G, and a subset of pairwise disjoint segments corresponds to an independent set in G (an anti-clique also called a stable). Consider the complement graph G = (V,E) where E = \E, with = {{V _i,V _j}  :  i ⁄= j} the full edge set. G is the disjointness graph [3] of the segments (i.e., an edge between nodes if and only if corresponding segments are disjoint), and we have G ∪G = K_n, the clique of size n.

Ramsey-type theorems are characterizing the following types of questions: “How large a structure must be to guarantee a given property?” Surprisingly, complete disorder is impossible! That is, there always exists (some) order in structures!

Define the Ramsey number R(s,t) as the minimum number n such that any graph with |V | = n nodes contains either an independent set of size s or a clique K_t of size t.

One can prove that those Ramsey numbers are all finite [4] (by proving the recursive formula R(s,t) ≤ R(s - 1,t) + R(s,t - 1) with terminal cases R(s,1) = R(1,t) = 1 for s,t ≥ 1), and that the following bound holds (due to the theorem of Erdös-Szekeres [2]):

When s = t, = is a central binomial coefficient that is upper bounded by 2^2s. Therefore the diagonal Ramsey number R(s) = R(s,s) is upper bounded by 2^2s. Furthermore, we have the following lower bound: 2 < R(s) when s ≥ 3 [2]. Thus s ≥⌊ log ₂n⌋. Erdös proved using a probabilistic argument [1] that there exists a graph G such that s ≤ 2log ₂n (G and G do not contain K_s subgraphs). It is proved in [3] (2017) a much stronger result that s = Ω(n) for intersection graphs of line segments: Thus there are always Ω(n) pairwise disjoint or pairwise intersecting segments in a set of n segments in general position.

In general, one can consider a coloring of the edges of the clique K_n into c colors, and asks for the largest monochromatic clique K_m in the edge-colored K_n. For the pairwise disjoint/intersecting line segments, we have c = 2: Say, we color edges red when their corresponding segments intersect and blue, otherwise.

Ramsey’s theorem [4] (1930) states that for all c, there exists n ≥ m ≥ 2 such that every c-coloring of K_n has a monochromatic clique K_m.

Let us conclude with the theorem on acquaintances (people who already met) and strangers (people who meet for the first time): In a group of six people, either at least three of them are pairwise mutual strangers or at least three of them are pairwise mutual acquaintances. Consider K₆ (n = 6, 15 edges), and color an edge in red if the edge people already met and in blue, otherwise. Then there is a monochromatic triangle (m = 3). Proof: R(3) = R(3,3) ≤ = 6.

Well, it is known that R(4) = 18 but R(5) is not known! We only know that 43 ≤ R(5) ≤ 48, 102 ≤ R(6,6) ≤ 165, etc. Quantum computers [5] can be used to compute Ramsey numbers!

Initially created 27th November 2017 (last updated November 30, 2017).

References