×

The unavoidable arrangements of pseudocircles. (English) Zbl 1422.52010

The well-known Erdős-Szekeres theorem states that for every fixed integer \(k \geq 3\), every sufficiently large set of points in general position in the plane contains \(k\) points in convex position. The dual version of the Erdős-Szekeres theorem for lines is that for every fixed \(k \geq 3\), every sufficiently large arrangement of lines in general position in the plane contains \(k\) lines in convex position, i.e. one of its cells is bounded by a \(k\)-gon, which necessarily contains a segment from each of the \(k\) lines. This dual Erdős-Szekeres theorem is the motivation for the paper under review. A simple arrangement of pseudolines is called cyclic if its pseudolines can be labelled \(1, 2, \dots,m\), so that each pseudoline \(i\in [m]\) intersects the pseudolines in \(\{1, 2, \dots , m\}\setminus \{i\}\) in increasing order. An arrangement of peudolines is called simple, if no 3 of them are incident to the same point.
The paper under review proves that for each fixed \(m \geq 1\), every sufficiently large simple arrangement of pseudolines has a cyclic subarrangement of size \(m\), and that this is the only unavoidable subarrangement. Furthermore, it characterizes the three type of arrangements of pseudocircles that are unavoidable in the same sense: for each fixed \(m \geq 1\), every sufficiently large simple arrangement of pseudocircles has a subarrangement of size \(m\) of one of the three types. (Recall that a pseudocircle is a simple closed curve in the sphere. Going with Grünbaum’s definiton, an arrangement of pseudocircles is a set of pseudocircles that pairwise intersect at exactly two points, at which they cross, and no three pseudocircles have a common point.)

MSC:

52C30 Planar arrangements of lines and pseudolines (aspects of discrete geometry)
52C40 Oriented matroids in discrete geometry
52C10 Erdős problems and related topics of discrete geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] B\'{a}r\'{a}ny, Imre; Rold\'{a}n-Pensado, Edgardo; T\'{o}th, G\'{e}za, Erd\H{o}s-Szekeres theorem for lines, Discrete Comput. Geom., 54, 3, 669-685 (2015) · Zbl 1326.52015 · doi:10.1007/s00454-015-9705-y
[2] Bokowski, J., Oriented matroids. Handbook of convex geometry, Vol. A, B, 555-602 (1993), North-Holland, Amsterdam · Zbl 0796.52001
[3] Erd\"{o}s, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · JFM 61.0651.04
[4] Goodman, Jacob E., Pseudoline arrangements. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., 83-109 (1997), CRC, Boca Raton, FL · Zbl 0914.51007
[5] Felsner, Stefan; Hurtado, Ferran; Noy, Marc; Streinu, Ileana, Hamiltonicity and colorings of arrangement graphs, Discrete Appl. Math., 154, 17, 2470-2483 (2006) · Zbl 1108.05058 · doi:10.1016/j.dam.2006.04.006
[6] Felsner, Stefan; Scheucher, Manfred, Arrangements of pseudocircles: triangles and drawings. Graph drawing and network visualization, Lecture Notes in Comput. Sci. 10692, 127-139 (2018), Springer, Cham · Zbl 1503.52036
[7] Felsner, Stefan; Scheucher, Manfred, Arrangements of pseudocircles: triangles and drawings. Graph drawing and network visualization, Lecture Notes in Comput. Sci. 10692, 127-139 (2018), Springer, Cham · Zbl 1503.52036
[8] Goodman, Jacob E., Proof of a conjecture of Burr, Gr\"{u}nbaum, and Sloane, Discrete Math., 32, 1, 27-35 (1980) · Zbl 0444.05029 · doi:10.1016/0012-365X(80)90096-5
[9] Gr\"{u}nbaum, Branko, Arrangements and spreads, iv+114 pp. (1972), American Mathematical Society Providence, R.I. · Zbl 0249.50011
[10] Harborth, Heiko; M\"{o}ller, Meinhard, The Esther Klein problem in the projective plane, J. Combin. Math. Combin. Comput., 15, 171-179 (1994) · Zbl 0807.51008
[11] Kang, Ross J.; M\"{u}ller, Tobias, Arrangements of pseudocircles and circles, Discrete Comput. Geom., 51, 4, 896-925 (2014) · Zbl 1298.52028 · doi:10.1007/s00454-014-9583-8
[12] Linhart, Johann; Ortner, Ronald, On the combinatorial structure of arrangements of oriented pseudocircles, Electron. J. Combin., 11, 1, Research Paper 30, 13 pp. (2004) · Zbl 1053.52030
[13] Negami, Seiya, Ramsey theorems for knots, links and spatial graphs, Trans. Amer. Math. Soc., 324, 2, 527-541 (1991) · Zbl 0721.57004 · doi:10.2307/2001731
[14] Ortner, Ronald, Embeddability of arrangements of pseudocircles into the sphere, European J. Combin., 29, 2, 457-469 (2008) · Zbl 1144.52023 · doi:10.1016/j.ejc.2007.02.006
[15] Pach, J\'{a}nos; Solymosi, J\'{o}zsef; T\'{o}th, G\'{e}za, Unavoidable configurations in complete topological graphs, Discrete Comput. Geom., 30, 2, 311-320 (2003) · Zbl 1042.05030 · doi:10.1007/s00454-003-0012-9
[16] Ram\'{i}rez Alfons\'{i}n, J. L., Spatial graphs, knots and the cyclic polytope, Beitr\"{a}ge Algebra Geom., 49, 2, 301-314 (2008) · Zbl 1216.05087
[17] Richter-Gebert, J\`“{u}rgen; Ziegler, G\'”{u}nter M., Oriented matroids. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., 111-132 (1997), CRC, Boca Raton, FL · Zbl 0902.05015
[18] Tantau, Till, Graph drawing in Ti{\it k}Z. Graph drawing, Lecture Notes in Comput. Sci. 7704, 517-528 (2013), Springer, Heidelberg · Zbl 1377.68188 · doi:10.1007/978-3-642-36763-2\_46
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.