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
Additional Information
- Carolina Medina
- Affiliation: Department of Mathematics, University of California, Davis, California 95616
- MR Author ID: 1088546
- Email: carolitomedina@gmail.com
- Jorge Ramírez-Alfonsín
- Affiliation: IMAG, Université de Montpellier, CNRS, Montpellier, France; and Unité Mixte Internationale CNRS-CONACYT-UNAM “Laboratoire Solomon Lefschetz”, Cuernavaca, Mexico
- Email: jorge.ramirez-alfonsin@umontpellier.fr
- Gelasio Salazar
- Affiliation: Instituto de Física, Universidad Autónoma de San Luis Potosí, Mexico; and Unité Mixte Internationale CNRS-CONACYT-UNAM “Laboratoire Solomon Lefschetz”, Cuernavaca, Mexico
- MR Author ID: 609449
- Email: gsalazar@ifisica.uaslp.mx
- Received by editor(s): August 18, 2018
- Received by editor(s) in revised form: October 19, 2018
- Published electronically: March 26, 2019
- Additional Notes: The first author was supported by Fordecyt grant 265667.
The second author was partially supported by PICS07848 grant and by Program MATH-AMSUD 41327ZL - FLaNASAGraTA
The third author was supported by Conacyt grant 222667 and by FRC-UASLP - Communicated by: Patricia L. Hersh
- © Copyright 2019 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 147 (2019), 3165-3175
- MSC (2010): Primary 52C30; Secondary 05C10, 52C40
- DOI: https://doi.org/10.1090/proc/14450
- MathSciNet review: 3973915