LIPIcs.SoCG.2023.17.pdf
- Filesize: 0.8 MB
- 14 pages
Document
An Extension Theorem for Signotopes
Authors
Helena Bergold 
,
Stefan Felsner ,
Manfred Scheucher
-
Part of:
Volume:
39th International Symposium on Computational Geometry (SoCG 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-06-09
File
Document Identifiers
Author Details
Acknowledgements
We thank the anonymous reviewers for valuable comments.
Cite As Get BibTex
Helena Bergold, Stefan Felsner, and Manfred Scheucher. An Extension Theorem for Signotopes. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.17
Abstract
In 1926, Levi showed that, for every pseudoline arrangement 𝒜 and two points in the plane, 𝒜 can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in ℝ^d with a hyperplane containing d prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in ℝ³ which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks r ≥ 4 there exist signotopes which are not extendable for two prescribed points. Our conjecture is supported by examples in ranks 4, 6, 8, 10, and 12 that were found with a SAT based approach.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
- Mathematics of computing → Solvers
- Mathematics of computing → Enumeration
- Hardware → Theorem proving and SAT solving
- Theory of computation → Automated reasoning
- Theory of computation → Computational geometry
Keywords
- arrangement of pseudolines
- extendability
- Levi’s extension lemma
- arrangement of pseudohyperplanes
- signotope
- oriented matroid
- partial order
- Boolean satisfiability (SAT)
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alan Arroyo, Dan McQuillan, R. Bruce Richter, and Gelasio Salazar. Levi’s lemma, pseudolinear drawings of K_n, and empty triangles. Journal of Graph Theory, 87(4):443-459, 2018. URL: https://doi.org/10.1002/jgt.22167.
- Martin Balko. Ramsey numbers and monotone colorings. Journal of Combinatorial Theory, Series A, 163:34-58, 2019. URL: https://doi.org/10.1016/j.jcta.2018.11.013.
- Martin Balko, Radoslav Fulek, and Jan Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of K_n. Discrete & Computational Geometry, 53(1):107-143, 2015. URL: https://doi.org/10.1007/s00454-014-9644-z.
- Helena Bergold, Stefan Felsner, and Manfred Scheucher. Supplemental source code and data. URL: https://page.math.tu-berlin.de/~scheuch/supplemental/signotopes/extend/sigext_suppl_socg.zip.
- Helena Bergold, Stefan Felsner, and Manfred Scheucher. An extension theorem for signotopes. http://arxiv.org/abs/2303.04079, 2023.
- Armin Biere. PicoSAT essentials. Journal on Satisfiability, Boolean Modeling and Computation (JSAT), 4:75-97, 2008. URL: http://satassociation.org/jsat/index.php/jsat/article/view/45.
- Armin Biere. CaDiCaL at the SAT Race 2019. In Proc. of SAT Race 2019 - Solver and Benchmark Descriptions, volume B-2019-1 of Department of Computer Science Series, pages 8-9. University of Helsinki, 2019. URL: http://researchportal.helsinki.fi/en/publications/proceedings-of-sat-race-2019-solver-and-benchmark-descriptions.
- Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. Oriented Matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1999. URL: https://doi.org/10.1017/CBO9780511586507.
- Stefan Felsner and Helmut Weil. Sweeps, Arrangements and Signotopes. Discrete Applied Mathematics, 109(1):67-94, 2001. URL: https://doi.org/10.1016/S0166-218X(00)00232-8.
- Jon Folkman and Jim Lawrence. Oriented matroids. Journal of Combinatorial Theory, Series B, 25(2):199-236, 1978. URL: https://doi.org/10.1016/0095-8956(78)90039-4.
- Jacob E. Goodman. Proof of a conjecture of Burr, Grünbaum, and Sloane. Discrete Mathematics, 32(1):27-35, 1980. URL: https://doi.org/10.1016/0012-365X(80)90096-5.
- Jacob E. Goodman and Richard Pollack. Three points do not determine a (pseudo-) plane. Journal of Combinatorial Theory, Series A, 31(2):215-218, 1981. URL: https://doi.org/10.1016/0097-3165(81)90017-0.
- Alexey Ignatiev, Antonio Morgado, and Joao Marques-Silva. PySAT: A Python toolkit for prototyping with SAT oracles. In SAT, pages 428-437, 2018. URL: https://doi.org/10.1007/978-3-319-94144-8_26.
-
Friedrich Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse, 78:256-267, 1926.
-
Yuri I. Manin and Vadim V. Schechtman. Arrangements of hyperplanes, higher braid groups and higher bruhat orders. Advanced Studies in Pure Mathematics, pages 289-308, 1989.
- Hiroyuki Miyata. On combinatorial properties of points and polynomial curves. http://arXiv.org/abs/1703.04963, 2021.
- OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at URL: http://oeis.org.
- Jürgen Richter-Gebert. Oriented matroids with few mutations. In Discrete & Computational Geometry, volume 10, pages 251-269. Springer, 1993. URL: https://doi.org/10.1007/BF02573980.
- Marcus Schaefer. A proof of Levi’s extension lemma. http://arXiv.org/abs/1910.05388, 2019.
- Ilan Schnell et al. pycosat: bindings to PicoSAT (a SAT solver). http://pypi.python.org/pypi/pycosat.
- Günter M. Ziegler. Higher Bruhat orders and cyclic hyperplane arrangements. Topology, 32(2):259-279, 1993. URL: https://doi.org/10.1016/0040-9383(93)90019-R.