2026-09-05T11:55:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25827 2026-06-23T12:59:07Z ddc:004 open_access

On Minimum Venn Diagrams Brenner, Sofia Gregor, Petr Mütze, Torsten Verciani, Francesco Venn diagram crossing conjecture hypercube partition An n-Venn diagram is a diagram in the plane consisting of n simple closed curves that intersect only finitely many times such that each of the 2ⁿ possible intersections of their interiors is represented by a single connected region. An n-Venn diagram has at most 2ⁿ-2 crossings, and if this maximum number of crossings is attained, then only two curves intersect in every crossing. To complement this, Bultena and Ruskey considered n-Venn diagrams that minimize the number of crossings, which implies that many curves intersect in every crossing. Specifically, they proved that the total number of crossings in any n-Venn diagram is at least L_n≔⌈(2ⁿ-2)/(n-1)⌉, and if this lower bound is attained, then essentially all n curves intersect in every crossing. Diagrams achieving this bound are called minimum Venn diagrams, and are known only for n ≤ 7. Bultena and Ruskey conjectured that they exist for all n ≥ 8. In this work, we establish an asymptotic version of their conjecture. For n = 8 we construct a diagram with 40 crossings, only 3 more than the lower bound L₈ = 37. Furthermore, for every n of the form n = 2^k for some integer k ≥ 4, we construct an n-Venn diagram with at most (1+33/8n)L_n = (1+o(1))L_n many crossings. Via a doubling trick this also gives (n+m)-Venn diagrams for all 0 ≤ m < n with at most 40⋅ 2^m crossings for n = 8 and at most (1+33/8n) (n+m)/n L_{n+m} = (2+o(1))L_{n+m} many crossings for k ≥ 4. In particular, we obtain n-Venn diagrams with the smallest known number of crossings for all n ≥ 8. Our constructions are based on partitions of the hypercube into isometric paths and cycles, using a result of Ramras. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sofia Brenner and Petr Gregor and Torsten Mütze and Francesco Verciani 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.21 urn:nbn:de:0030-drops-258278 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode