Disproving two conjectures on the Hamiltonicity of Venn diagrams

Venn diagrams are a popular tool to illustrate the relations between sets and operations on them, such as union and intersection, or the well-known inclusion-exclusion principle. Historically, these diagrams were introduced by John Venn (1834-1923) in the context of formal logic. Most of these illustrations depict the Venn diagram with three sets represented by unit circles. It may even come to a surprise that Venn diagrams exist for any number of sets, not just three. In 1984, Peter Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves by the addition of a suitable curve. In this work, we construct counterexamples to Winkler's conjecture for all n>=6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n = 6 curves (even their number was not previously known), among which we found 72 counterexamples. Furthermore, we also disprove another conjecture about the Hamiltonicity of the arrangement graph of a Venn diagram. Specifically, while working on Winkler's conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n>=4.

This is joint work with Sofia Brenner, Linda Kleist, Christian Rieck and Francesco Verciani.