CS Paper Radar

Simple symmetric Venn diagrams with 17, 19 and 23 curves

Chris Dzoba

cs.CG math.COcs.DM ·submitted 2026-09-22 15:02 UTC · v3
code/dataunusual

Abstract

We exhibit simple, rotationally symmetric Venn diagrams with 17 curves, with 19 curves and with 23 curves: $n$ Jordan curves carried to one another by rotation through $2π/n$, with every one of the $2^n$ regions present and connected and, since the diagrams are simple, every crossing on exactly two curves. Symmetric Venn diagrams exist for every prime number of curves (Griggs, Killian and Savage, 2004), but those diagrams have many curves through a point; simple ones were known only up to 13 curves (Mamakani and Ruskey, 2014). Four 17-curve, twelve 19-curve and six 23-curve diagrams were found by a Metropolis walk on rotation-invariant quadrangulations of the sphere in which regions may temporarily be duplicated, started from the Griggs-Killian-Savage diagram with its multiple crossings resolved. At 23 curves the walk was held for two weeks by duplicated regions near the poles; the two lineages that finished were the first whose $E=92$ states had none. Every diagram is given by a machine-checkable certificate; one certificate each of the 17-, 19- and 23-curve sizes has been verified by a formal proof in Lean 4. All of the diagrams are non-monotone, which is why the crossing-sequence searches that found the 11- and 13-curve diagrams could not have found them.

Comment
15 pages, 2 figures. Certificates, independent checker, Lean 4 verifications and search code are archived at doi:10.5281/zenodo.22885649 and at https://github.com/dzoba/venn17. v3: twelve 19-curve and six 23-curve diagrams (was nine and five); Lean 4 verification of a 23-curve certificate; dual-depth measurement of the 23-curve diagram

Closest papers

Nearest neighbours by meaning across the whole index.

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

cs.CG math.CO ·2026-11-01 ·Ankan Sadhu
theory similarity 0.53
Abstract · 6 pages, 1 figure

For every fixed integer $k\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\ge3$, removing a small disk around each vertex turns the drawing into a family of arcs on a sphere with $n$ boundary circles. Each arc joins two different boundary circles, and different edges have different unordered pairs of endpoint circles. The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most $k-1$. Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the $n$-holed sphere has linearly many edges and triangles.

0.54

Symmetric, rational and infinitely many $(23_4)$ configurations, and the end of the existence problem for geometric $(n_4)$ configurations

cs.CG math.COcs.DM ·2026-10-08 ·Wenhao Lu
publishedtheory similarity 0.51
Abstract · To be presented at the 2027 Joint Mathematics Meetings, Chicago (AMS Contributed Paper Session on Combinatorics, I, January 12, 2027)

A geometric $(n_4)$ configuration is a set of $n$ points and $n$ lines in the real projective plane such that every point lies on exactly four of the lines and every line contains exactly four of the points. The question of which $n$ admit such a configuration was posed by Grünbaum in 2000, and successive work of Bokowski, Grünbaum, Schewe, Pilaud and Cuntz settled every case but $n=23$. We settle this last case by bounding the symmetry of such configurations and classifying the most symmetric ones exactly. We prove that for every prime $n\equiv3\pmod4$ the group of projective symmetries of a geometric $(n_4)$ configuration has order at most four, explaining why symmetric constructions failed at $n=23$, and the same argument bounds the symmetry of $(n_5)$ configurations for primes $n\not\equiv1\pmod5$. Reducing the Klein four-group case to 4021 bilinear polynomial systems and solving all of them exactly with Gröbner bases, we show that exactly two $(23_4)$ configurations reach this bound up to projective equivalence and that there are no others even over $\mathbb{C}$. Both are self-polar; the first has integer coordinates and the second is defined over $\mathbb{Q}(\sqrt{17})$ but not over $\mathbb{Q}$. Consequently geometric $(n_4)$ configurations exist if and only if $n\ge18$ and $n\ne19$. The same classification recovers Cuntz's $(22_4)$ and $(26_4)$ configurations and finds three new combinatorial types at $n=22$ and $94$ at $n=26$. Among self-polar $(23_4)$ configurations with a single involution we find $50$ more, defined over number fields of degree at most $7$. Four of them deform in one-parameter families, and computing three of these exactly, one birational to the modular curve $X_1(11)$, we prove that there are infinitely many geometric $(23_4)$ configurations, among them infinitely many with rational coordinates that are self-polar and have no projective symmetry.

0.35

Exact curve counting of given word length on the once-punctured torus

cs.CG math.GTmath.CO ·2026-09-01 ·Filippo Baroni, David Fisac, Mingkun Liu
unusual similarity 0.49
Abstract · 25 pages, 8 figures

On the once-punctured torus, we give an exact formula for the number of curves in any given mapping class group orbit of given word length. This settles a conjecture of Chas in [Cha16].

0.29

New lower bounds for kissing numbers in dimensions 32-35 and 37-39

cs.DM math.MGcs.ITmath.CO ·2026-10-22 ·Qihong Lin
code/data similarity 0.49
Abstract · 8 pages. Certificates and verification programs: https://github.com/QH-Lin/kissing-number-32 (doi:10.5281/zenodo.23527725) and https://githu…

We show that the kissing numbers in dimensions 32, 33, 34, 35, 37, 38 and 39 are at least 352320, 370240, 390980, 415308, 499816, 605322 and 768916, improving the previous bounds 347584, 364736, 384836, 409676, 498024, 591900 and 763668. Except in dimension 38, the configurations are those of Edel, Rains and Sloane with new binary constant-weight codes of weight 8 and minimum distance 8 in the middle layer; each additional word adds 128 points. In dimension 38 we add 6855 antipodal pairs of vectors of the second shell of the Leech lattice to the empty equator of Kravatskiy's 591612-point configuration, where 144 pairs were known; this is an independent set problem in a regular graph of degree 11178 on 8386560 vertices. The codes and lines were found by local search, and all configurations were checked pair by pair in exact integer arithmetic.

0.40

A Collapse Process for Farthest Voronoi Diagrams of Lines in Three Dimensions

cs.CG ·2026-09-24 ·Evanthia Papadopoulou, Martin Suderland, Zeyu Wang
similarity 0.47
Abstract

We study a \emph{collapse process} to construct the farthest Voronoi diagram of lines in three dimensions, given a spherical map of the diagram's unbounded features. The collapse process sweeps through the diagram in order of decreasing distance from the farthest lines. It follows the \emph{shrinking map}, a cell complex on a topological sphere that encodes the locus of points with a fixed farthest distance. We show that, in three dimensions, the collapse process has exactly four non-terminal local event types that change the structure of the shrinking map: \emph{deletion, swap, local minimum}, and \emph{local maximum} events; plus one terminal event. This list is complete. We give intrinsic three-dimensional geometric descriptions of the four non-terminal events. First, we classify the two vertex-related events, deletion and swap events, by the spherical convex hull of the four tangent points from a vertex to its four defining lines. Then, we analyze the events related to the local extrema of the distance function along the trisector of three lines. We show that the distance function along a trisector has at most $4$ local maxima and $8$ local minima, and that both bounds are tight. The extrema can be found via a polynomial of degree $12$. As a byproduct, this gives a direct method for finding the smallest sphere tangent to three given lines. At each local extremum, the tangent sphere touches the three lines at points lying on a great circle. The collapse process and the completeness of the event list also apply, under similar general position assumptions, to the farthest Voronoi diagram of convex sites under strictly convex distance functions.

0.38

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.47
Abstract

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

0.39

Biplanar graphs with independence number two are 9-colorable

cs.LO math.CO ·2026-09-23 ·Stefan Szeider
theoryhot direction similarity 0.47
Abstract

A graph is biplanar if it is the union of two planar graphs on the same vertex set. The largest chromatic number of a biplanar graph is known to lie between 9 and 12. The lower bound comes from Sulanke's graph, which has independence number 2, and a biplanar graph on 19 vertices with independence number 2 would have chromatic number at least 10. Gethner and Sulanke asked in 2009 whether such a graph exists. We show that it does not, and more generally that every biplanar graph with independence number at most 2 is 9-colorable. The proof embeds a hypothetical counterexample in the union of two sphere triangulations, enumerates with SAT modulo symmetries the 3271 graphs that pass a necessary filter for the complement of such a union, and shows with a SAT solver that none of them is such a complement; a matching argument reduces the general statement to this computation and one further case on 18 vertices. The computational part of the proof, including the completeness of the enumeration and every refutation, is checked in Lean 4, assuming three classical facts about planar graphs. The Lean development, the SAT instances, and the enumeration certificates are available on Zenodo.

0.24

Realizing graph automorphisms as geometric symmetries of straight line drawings

cs.CG math.COmath.GR ·2026-10-26 ·Saul D. Freedman, Melissa Lee, Dragan Marušič, Tomaž Pisanski
similarity 0.46
Abstract · 20 pages, comments welcome

Given a finite graph $G$, we characterize the automorphisms and automorphism groups of $G$ that can be realized as geometric symmetries and symmetry groups of straight line drawings of $G$ in the plane. In doing so, we correct a previous version of this characterization from the literature. As an application, we show that the graphs recently constructed by the first two authors to disprove the Polycirculant Conjecture, which have orders $16{,}464^k$ for each positive integer $k$, are the first known vertex-transitive graphs with no non-trivial realizable geometric symmetries. We also construct infinite families of graphs that exhibit all possible kinds of geometric symmetry.

0.22