Line Configurations and the Erdos-Hajnal Conjecture
Joshua Cooper · arXiv (Cornell University) · 2004
Define a set of lines in R 3 to be “stacked ” with respect to v ∈ R 3 if, from a point far away in the direction of v, the lines are linearly ordered by the “crossing over ” relation. Given a collection of skew lines and a point v, we ask, what is the largest stacked subset that must be present among the lines? This question is intimately related to the well-known Erdős-Hajnal conjecture via the Milnor-Thom theorem, a staple of combinatorial geometry. We describe this connection, resolve a special case of the question, state a generalization – the “Geometric Erdős-Hajnal Conjecture ” – and prove it in dimensions 1 and 2. We also offer several related questions, including an intriguing reformulation of Erdős-Hajnal as a problem in the logic of random graphs and a simple question about decomposability of semi-algebraic sets. Suppose we have a collection L of n lines and a direction v in R 3. Define T to be the set of the pairs (ℓ1, ℓ2) ∈ L × L so that ℓ1 “crosses over ” ℓ2 from the perspective of a point very far away in the direction of v. If the lines are pairwise skew, then T is a tournament, and we may ask for the size of its largest transitive subtournament: a set of lines which are linearly ordered by the “crossing over ” relation, i.e., which appear to be “stacked ” (q.v. Figure 1). By Ramsey’s Theorem, every tournament, including T, must have a transitive subtournament of size Ω(log n). Perhaps we can hope for more, however: T is very special, in that it is the result of a very specific construction. Surely, not all T can arise in this way from line configurations in R 3...? Indeed, the answer is “no”. There are very few such tournaments. To see this, we first make precise the notion of “crossing over”. Parameterize lines in R 3 as follows. Consider the plane perpendicular to v that passes through the origin. Call this the xy-plane. Then, consider the two planes x = 1 and x = −1. Each line ℓ crosses