Investigating Simple Drawings of $K_n$ using SAT
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913775440887808 |
|---|---|
| author | Bergold, Helena Scheucher, Manfred |
| author_facet | Bergold, Helena Scheucher, Manfred |
| contents | We present a SAT framework which allows to investigate properties of simple drawings of the complete graph $K_n$ using the power of AI. In contrast to classic imperative programming, where a program is operated step by step, our framework models mathematical questions as Boolean formulas which are then solved using modern SAT solvers. Our framework for simple drawings is based on a characterization via rotation systems and finite forbidden substructures. We showcase its universality by addressing various open problems, reproving previous computational results and deriving several new computational results. In particular, we test and progress on several unavoidable configurations such as variants of Rafla's conjecture on plane Hamiltonian cycles, Harborth's conjecture on empty triangles, and crossing families for general simple drawings as well as for various subclasses. Moreover, based our computational results we propose some new challenging conjectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02650 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Investigating Simple Drawings of $K_n$ using SAT Bergold, Helena Scheucher, Manfred Computational Geometry Discrete Mathematics Combinatorics We present a SAT framework which allows to investigate properties of simple drawings of the complete graph $K_n$ using the power of AI. In contrast to classic imperative programming, where a program is operated step by step, our framework models mathematical questions as Boolean formulas which are then solved using modern SAT solvers. Our framework for simple drawings is based on a characterization via rotation systems and finite forbidden substructures. We showcase its universality by addressing various open problems, reproving previous computational results and deriving several new computational results. In particular, we test and progress on several unavoidable configurations such as variants of Rafla's conjecture on plane Hamiltonian cycles, Harborth's conjecture on empty triangles, and crossing families for general simple drawings as well as for various subclasses. Moreover, based our computational results we propose some new challenging conjectures. |
| title | Investigating Simple Drawings of $K_n$ using SAT |
| topic | Computational Geometry Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2504.02650 |