The unavoidable arrangements of pseudocircles

Medina, Carolina; Ramírez-Alfonsín, Jorge; Salazar, Gelasio

doi:10.1090/proc/14450

The unavoidable arrangements of pseudocircles
HTML articles powered by AMS MathViewer

by Carolina Medina, Jorge Ramírez-Alfonsín and Gelasio Salazar PDF

Proc. Amer. Math. Soc. 147 (2019), 3165-3175 Request permission

Abstract:

A fact closely related to the classical Erdős-Szekeres theorem is that cyclic arrangements are the only unavoidable simple arrangements of pseudolines: for each fixed $m\ge 1$, every sufficiently large simple arrangement of pseudolines has a cyclic subarrangement of size $m$. In the same spirit, we show that there are three unavoidable arrangements of pseudocircles.

References

Imre Bárány, Edgardo Roldán-Pensado, and Géza Tóth, Erdős-Szekeres theorem for lines, Discrete Comput. Geom. 54 (2015), no. 3, 669–685. MR 3392972, DOI 10.1007/s00454-015-9705-y
J. Bokowski, Oriented matroids, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 555–602. MR 1242990
P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470. MR 1556929
Jacob E. Goodman, Pseudoline arrangements, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 83–109. MR 1730161
Stefan Felsner, Ferran Hurtado, Marc Noy, and Ileana Streinu, Hamiltonicity and colorings of arrangement graphs, Discrete Appl. Math. 154 (2006), no. 17, 2470–2483. MR 2272980, DOI 10.1016/j.dam.2006.04.006
Stefan Felsner and Manfred Scheucher, Arrangements of pseudocircles: triangles and drawings, Graph drawing and network visualization, Lecture Notes in Comput. Sci., vol. 10692, Springer, Cham, 2018, pp. 127–139. MR 3773232
Stefan Felsner and Manfred Scheucher, Arrangements of pseudocircles: triangles and drawings, Graph drawing and network visualization, Lecture Notes in Comput. Sci., vol. 10692, Springer, Cham, 2018, pp. 127–139. MR 3773232
Jacob E. Goodman, Proof of a conjecture of Burr, Grünbaum, and Sloane, Discrete Math. 32 (1980), no. 1, 27–35. MR 588905, DOI 10.1016/0012-365X(80)90096-5
Branko Grünbaum, Arrangements and spreads, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10, American Mathematical Society, Providence, R.I., 1972. MR 0307027
Heiko Harborth and Meinhard Möller, The Esther Klein problem in the projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171–179. MR 1274574
Ross J. Kang and Tobias Müller, Arrangements of pseudocircles and circles, Discrete Comput. Geom. 51 (2014), no. 4, 896–925. MR 3216670, DOI 10.1007/s00454-014-9583-8
Johann Linhart and Ronald Ortner, On the combinatorial structure of arrangements of oriented pseudocircles, Electron. J. Combin. 11 (2004), no. 1, Research Paper 30, 13. MR 2056082
Seiya Negami, Ramsey theorems for knots, links and spatial graphs, Trans. Amer. Math. Soc. 324 (1991), no. 2, 527–541. MR 1069741, DOI 10.1090/S0002-9947-1991-1069741-9
Ronald Ortner, Embeddability of arrangements of pseudocircles into the sphere, European J. Combin. 29 (2008), no. 2, 457–469. MR 2388382, DOI 10.1016/j.ejc.2007.02.006
János Pach, József Solymosi, and Géza Tóth, Unavoidable configurations in complete topological graphs, Discrete Comput. Geom. 30 (2003), no. 2, 311–320. U.S.-Hungarian Workshops on Discrete Geometry and Convexity (Budapest, 1999/Auburn, AL, 2000). MR 2007968, DOI 10.1007/s00454-003-0012-9
J. L. Ramírez Alfonsín, Spatial graphs, knots and the cyclic polytope, Beiträge Algebra Geom. 49 (2008), no. 2, 301–314. MR 2468058
Jürgen Richter-Gebert and Günter M. Ziegler, Oriented matroids, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 111–132. MR 1730162
Till Tantau, Graph drawing in TikZ, Graph drawing, Lecture Notes in Comput. Sci., vol. 7704, Springer, Heidelberg, 2013, pp. 517–528. MR 3067257, DOI 10.1007/978-3-642-36763-2_{4}6