Erdos-Hajnal Sets and Semigroup Decompositions
| dc.creator | Cooper, Joshua N. | |
| dc.date | 2004-08-29 | |
| dc.date | 2004-09-14 | |
| dc.date.accessioned | 2026-07-07T05:11:37Z | |
| dc.date.available | 2026-07-07T05:11:37Z | |
| dc.description | Define a set of lines in $R^3$ to be ``stacked'' with respect to $v \in R^3$ if, from a vantage 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, which appears in a 2000 paper of Erdos, Hajnal and Pach, is intimately related to the well-known Erdos-Hajnal conjecture via the Milnor-Thom theorem. It was recently resolved by a powerful and very general theorem of Alon, Pach, Pinchasi, Radoicic, and Sharir. We describe these results and discuss several related issues, including a generalization to ``Erdos-Hajnal sets'' and an intriguing problem concerning the decomposability of semi-algebraic sets: Do all semi-algebraic sets belong to the set algebra generated by semigroups in $R^d$? Our main result is a resolution of this question in dimensions 1 and 2. | |
| dc.description | 12 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/math/0408397 | |
| dc.identifier | http://arxiv.org/abs/math/0408397 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72308 | |
| dc.subject | Combinatorics | |
| dc.subject | Algebraic Geometry | |
| dc.subject | 05C69 (Primary); 05C20, 14P10, 14P25, 20M99 (Secondary) | |
| dc.title | Erdos-Hajnal Sets and Semigroup Decompositions | |
| dc.type | text |