2025/11/12 by Brenner, Sofia, Gregor, Petr, Mütze, Torsten +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2511.09230
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 2n possible intersections is represented by a single connected region. An n-Venn diagram has at most 2n-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 Ln:=\lceil(2n-2)/(n-1)\rceil, 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 asympototic version of their conjecture. For n=8 we construct a diagram with 40 crossings, only 3 more than the lower bound L8=37. Furthermore, for every n of the form n=2k for some integer k≥ 4, we construct an n-Venn diagram with at most (1+(33)/(8n))Ln=(1+o(1))Ln many crossings. Via a doubling trick this also gives (n+m)-Venn diagrams for all 0≤ m