Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams

Problems on Venn diagrams such as Winkler’s conjecture are best discussed by considering the dual graph of the Venn diagram, i.e., the plane graph that has a vertex inside every region, and edges connecting vertices corresponding to neighboring regions; see Figure 2. For this, we consider the $n$-dimensional hypercube $Q_n$, or $n$-cube for short, the graph formed by all bitstrings of length $n$, with an edge between any two bitstrings that differ in a single bit. The dual graph $Q(D)$ of a simple $n$-Venn diagram $D$ satisfies the following properties:

1

It is a connected subgraph of $Q_n$ that is also spanning, i.e., all $2^n$ vertices are present. Specifically, the vertex in $Q(D)$ corresponding to a region of the diagram $D$ is the characteristic vector of the inside/outside relation with respect to each curve, where 0 and 1 represent outside and inside, respectively.¹¹1When considering the diagram in the plane, then the inside and outside of a curve $C$ are the bounded and unbounded region of ${ℝ}^2\setminus C$, respectively.

2

It is a plane quadrangulation, i.e., it is drawn in the plane without edge crossings, and every face (including the outer face) is a 4-cycle.

3

For every position $i\in \{1,\mathrm{\dots },n\}$ and every bit $b\in \{0,1\}$, the subgraph of $Q(D)$ induced by all vertices $x$ with $x_i=b$ is connected.

Conversely, the dual of any subgraph of $Q_n$ satisfying these properties is an $n$-Venn diagram.

We refer to subgraphs of $Q_n$ satisfying 1–3, which are the duals of $n$-Venn diagrams, as $n$-Venn quadrangulations.

Extending the diagram $D$ by a single curve means that the new curve has to enter and leave every region of $D$ exactly once, splitting it into two, one of them inside and the other one outside the newly added curve. This corresponds to traversing a Hamilton cycle in the dual graph $Q(D)$, i.e., a cycle in the graph that visits every vertex exactly once; see Figure 2 (b)+(c).

Conjecture 1 can thus be restated equivalently as follows: For $n\ge 2$, every $n$-Venn quadrangulation admits a Hamilton cycle.

As $Q_n$ is a bipartite graph, Venn quadrangulations are bipartite, too. A necessary condition for the existence of a Hamilton cycle in a bipartite graph is the existence of a perfect matching. We provide counterexamples to Conjecture 1 by constructing, for every $n\ge 6$, an $n$-Venn quadrangulation that has no perfect matching and thus no Hamilton cycle. One of our counterexamples for $n=6$ is shown in Figure 3.

As mentioned before, for $n\le 5$ all simple $n$-Venn diagrams are extendable, so Theorem 2 is best possible in the sense that the counterexamples for $n=6$ are minimal. In fact, as part of our proof of Theorem 2 we computed all distinct 6-Venn diagrams and analyzed their properties, summarized in the next theorem, Figure 4 and Table 1. Specifically, we consider two diagrams the same if they differ only by mirroring and/or stereographic projection. Equivalently, we count their dual $n$-Venn quadrangulations up to graph isomorphism. Prior to this work, the number of simple $n$-Venn diagrams was only known up to $n\le 5$. Specifically, for each $n\le 4$ there is only one, and for $n=5$ there are 20 [6, 10].

To state the next theorem, we define a few relevant properties. A $k$-region in an $n$-Venn diagram is a region that lies inside of exactly $k$ of the $n$ curves (and outside of the remaining $n-k$ curves). A monotone Venn diagram is one in which for every , every $k$-region is adjacent to both a $(k-1)$-region and a $(k+1)$-region. Bultena, Grünbaum and Ruskey [3] proved that monotone diagrams are precisely the ones that can be drawn such that every curve has a convex shape. An exposed diagram is one in which the outer region is bounded by all $n$ curves. It is not hard to see that any monotone diagram is also exposed. Chilakamarri, Hamburger and Pippert [5] constructed $n$-Venn diagrams for every $n$ in which all regions are (combinatorial) triangles, quadrangles or pentagons, in particular, they are not exposed for $n\ge 6$.

As a consequence of Theorem 3, there are 6-Venn quadrangulations (in total $72-17=55$ many) that have a perfect matching but no Hamilton cycle, and 6-Venn quadrangulations (in total $60-17=43$ many) that have a perfect matching but no Hamilton path.

The programs we used for computing all simple 6-Venn diagrams and the result files with all 6-Venn quadrangulations are available for download [2].

We disprove Conjecture 5 by providing counterexamples for all $n\ge 4$. Similarly to Theorem 2, our counterexamples have an even number of vertices and do not admit a perfect matching, which would be necessary for having a Hamilton cycle. One of the counterexamples for $n=4$ is shown in Figure 6.

We remark that the counterexamples constructed in the proof of Theorem 6, including the one shown in Figure 6, are actually monotone. With straightforward modifications the diagrams can also be made crossing, i.e., such that whenever two curves meet, they cross.

Any cycle $C=(x_1,\mathrm{\dots },x_{\mathrm{\ell }})$ in $Q_{n-1}$ can be described by the first vertex $x_1$ and the sequence of edge types $({\tau }_1,\mathrm{\dots },{\tau }_{\mathrm{\ell }})$, i.e., ${\tau }_i\in [n-1]$ is the type of the edge of $C$ between vertices $x_i$ and $x_{i+1}$ for $i=1,\mathrm{\dots },\mathrm{\ell }$ (where $x_{\mathrm{\ell }+1}:=x_1$). The automorphisms of the hypercube are given by all permutations of positions and taking the exclusive-or with an arbitrary fixed bitstring of length $n$. Consequently, we can assume w.l.o.g. that $x_1=0^{n-1}$. Note that for any sequence $\tau =({\tau }_1,\mathrm{\dots },{\tau }_{\mathrm{\ell }})$ of edge types from $[n-1]$, there is a unique permutation $\sigma$ on $[n-1]$ such that $\sigma (\tau )=(\sigma ({\tau }_1),\mathrm{\dots },\sigma ({\tau }_{\mathrm{\ell }}))$ is lexicographically minimal, i.e., for every prefix $(\sigma ({\tau }_1),\mathrm{\dots },\sigma ({\tau }_p))$, $p=1,\mathrm{\dots },\mathrm{\ell }$, of the permuted sequence, if it contains $r$ different types, then these are the types $1,\mathrm{\dots },r$. Therefore, we can assume w.l.o.g. that $\tau =\sigma (\tau )$ is lexicographically minimal and furthermore, for every cyclic shift and/or reversal ${\tau }^{\prime }$ of the sequence $\tau$, we have $\tau {\le }_{\mathrm{lex}}\sigma ({\tau }^{\prime })$. Factoring out the automorphisms of $Q_{n-1}$ in this way drastically reduces the number of distinct cycles $C$ that need to be considered.

In the following, we describe another observation that allows us to restrict the lengths of the boundary cycles to consider. As mentioned before, the total number of crossings in a simple $n$-Venn diagram $D$ is $2^n-2$. Clearly, this number equals the number of faces of $Q(D)$. The number of vertices of $Q(D)$ is $2^n$, and therefore Euler’s formula yields $2^{n+1}-4$ for the number of edges of $Q(D)$. These edges split into $n$ different matchings $M_1,M_2,\mathrm{\dots },M_n$ according to their types, and we can therefore always guarantee that one matching $M_i$ has size $|M_i|\ge \frac{2^{n+1}-4}{n}$, and the fraction on the right should be rounded up to the next even integer, because the corresponding boundary cycle in the hypercube must have even integral length. For $n=6$ this yields the lower bound $|M_i|\ge 22$ for one of the matchings. By symmetry, we can thus restrict our search to cycles $C$ in $Q_5$ of lengths $22,24,26,28,30,32$. Note that if $C$ has the maximum length $2^{n-1}$, then it is a Hamilton cycle in $Q_{n-1}$, and the resulting $n$-Venn diagram $H$ obtained by pairing two compatible $C$-quadrangulations is reducible and thus extendable.

The number of cycles of lengths $22,24,26,28,30,32$ in $Q_5$ up to automorphisms is $819.049,\mathrm{2.168.994},\mathrm{3.859.153},\mathrm{4.028.138},\mathrm{1.934.320},237.675$, respectively. The last number agrees with the fifth entry of OEIS sequence A159344, as it should.

For a fixed cycle $C$ in $Q_{n-1}$ as computed in the previous step, we aim to compute all $C$-quadrangulations. This is done recursively, by filling the inside of $C$ with 4-faces, one at a time. In each step, the current partial $C$-quadrangulation $P$ has an inner face $B$ that still needs to be quadrangulated; see Figure 8 (b). For this we consider every edge $e$ along $B$, and every 4-cycle $F$ in $Q_{n-1}$ that contains $e$ (there are $n-3$ such 4-cycles). Every such 4-cycle $F$ containing $e$ has two additional vertices $u$ and $v$. We locate $u$ and $v$ in $P$ and distinguish the following cases: If $u$ and $v$ are on $B$ but in the wrong cyclic order, then $F$ is excluded, i.e., it will not be added to $P$ as a 4-face. Similarly, if $u$ or $v$ are present in $P$ but not on $B$, then $F$ is excluded. These two cases are shown in Figure 9 (c), respectively. If $u$ and $v$ are on $B$ but not next to $e$ (Figure 9 (b)), then $F$ is ignored for this recursion step (because including $F$ would split the inner face bounded by $B$ into two separate faces). If $u$ and $v$ are next to $e$ on $B$ or not in $P$ (Figure 9 (a) shows the six possible such cases), then $F$ is eligible for a branching step. Specifically, we branch and recurse on the two possibilities of either including $F$, updating $B$ accordingly, or excluding $F$, which does not change $B$. Some care has to be taken to choose a clever branching order to avoid recomputing the same $C$-quadrangulation along different insertion orderings of its 4-faces, and also to keep the recursion tree small, i.e., to enforce and detect dead ends quickly (for details, see our C++ implementation [2]). Such a dead end would be an edge $e$ on $B$ for which all 4-cycles $F$ containing $e$ are excluded (apart possibly from one that can be included “behind” $e$).

For a fixed cycle $C$ of $Q_{n-1}$, after computing all $C$-quadrangulations, we consider all pairs $P,P^{\prime }$ of them, and check if $P$ and $P^{\prime }$ are compatible, i.e., whether the graph $H$ defined in (1) satisfies condition 3. This is achieved by a simple graph search, run separately for every bit position $i\in [n]$ and bit value $b\in \{0,1\}$, i.e., $2n$ searches in total. This can be slightly optimized by first doing the graph searches separately within each graph $P$ and $P^{\prime }$, checking whether and how the subgraphs given by a fixed $i\in [n]$ and $b\in \{0,1\}$ intersect with $C$ (already this may lead to discarding $P$ or $P^{\prime }$, independently of the other), and then computing the overall connectivity resulting from that.

After computing all $n$-Venn quadrangulations as described in the previous step, we need to filter out duplicates, i.e., graphs that are isomorphic copies. These isomorphic copies can arise from two different boundary cycles $C$ and $C^{\prime }$, obtained by splitting the same diagram along two different curves. The filtering is achieved by first computing a canonical graph labeling, available in SageMath via the function canonical_label() (which internally uses the tool bliss), and conversion into graph6 format, so that the isomorphism test becomes a string comparison.

The different properties of a given $n$-Venn quadrangulation can be checked straightforwardly, either by efficient algorithms (perfect matchings, monotone, exposed, reducible) or by brute-force (Hamilton cycle/path), using standard SageMath functions. For $n=6$ there are relatively few graphs and they are relatively small and sparse (64 vertices and 124 edges), so this is fast enough.