Erdý os-Hajnal Sets and Semigroup Decompositions
Joshua Cooper · arXiv (Cornell University) · 2008
AbstractDefine a set of lines in R 3 to be “stacked” with respect to v ∈ R 3 if, from avantage 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? Thisquestion, which appears in [6], is intimately related to the well-known Erd˝os-Hajnal conjecture via the Milnor-Thom theorem. It was recently resolved by apowerfuland very general theorem of Alon, Pach, Pinchasi, Radoiˇci´c, and Sharir([1]). We describe these results and discuss several related issues, including ageneralization to “Erd˝os-Hajnal sets” and an intriguing problem concerning thedecomposability of semi-algebraic sets: Do all semi-algebraic sets belong to theset algebra generated by semigroups in R d ? Our main result is a resolution ofthis question in dimensions 1 and 2. Suppose we have a collection L of n lines and a direction v in R 3 . Define T to bethe set of the pairs (l