On Minimum Venn Diagrams

Brenner, Sofia; Gregor, Petr; Mütze, Torsten; Verciani, Francesco

doi:10.4230/LIPIcs.SoCG.2026.21

On Minimum Venn Diagrams

Sofia Brenner

Institute of Mathematics, University of Kassel, Germany Petr Gregor

Department of Theoretical Computer Science and Mathematical Logic, Charles University, Prague, Czech Republic Torsten Mütze

Institute of Mathematics, University of Kassel, Germany Francesco Verciani

Institute of Mathematics, University of Kassel, Germany

Abstract

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^{n}$ possible intersections of their interiors is represented by a single connected region. An $n$ -Venn diagram has at most $2^{n}-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}\coloneq\lceil\frac{2^{n}-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\leq 7$ . Bultena and Ruskey conjectured that they exist for all $n\geq 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_{8}=37$ . Furthermore, for every $n$ of the form $n=2^{k}$ for some integer $k\geq 4$ , we construct an $n$ -Venn diagram with at most $(1+\frac{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\leq m<n$ with at most $40\cdot 2^{m}$ crossings for $n=8$ and at most $(1+\frac{33}{8n})\frac{n+m}{n}L_{n+m}=(2+o(1))L_{n+m}$ many crossings for $k\geq 4$ . In particular, we obtain $n$ -Venn diagrams with the smallest known number of crossings for all $n\geq 8$ . Our constructions are based on partitions of the hypercube into isometric paths and cycles, using a result of Ramras.

Keywords and phrases:

Venn diagram, crossing, conjecture, hypercube, partition

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry ; Mathematics of computing

\rightarrow

Discrete mathematics

Related Version:

Full Version: https://arxiv.org/abs/2511.09230 [1]

Funding:

Sofia Brenner, Torsten Mütze, and Francesco Verciani were supported by German Science Foundation (DFG) grant 522790373. Sofia Brenner also acknowledges funding by a postdoc fellowship of the German Academic Exchange Service (DAAD).

DOI:

10.4230/LIPIcs.SoCG.2026.21

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

An $n$ -Venn diagram is a collection of $n\geq 1$ simple closed curves in the plane that intersect in only finitely many points and that create exactly $2^{n}$ connected regions, one for every possible combination of being inside or outside with respect to each curve. It is easy to see that in any intersection point of at least two curves, at least two of them must cross, and thus we refer to any such intersection point as a crossing. A Venn diagram is simple if every crossing involves only two curves; see Figure 1.

Venn diagrams are an appealing tool to visualize sets and their containment relations, and they are named after the English mathematician John Venn (1834–1923), who used them in the context of propositional logic [24]. Despite the simple definition, many questions about Venn diagrams lead to interesting and challenging mathematical and computational problems, which triggered a long and fruitful line of research devoted to them; see Ruskey and Weston’s survey [19] and the many beautiful illustrations therein. These problems touch and connect various areas such as discrete geometry, graph drawing, graph theory, poset theory, coding theory, and enumerative combinatorics.

Figure 1: Simple Venn diagrams for

n=3,4,5

, maximizing the number of crossings. For

n=3,4,5

the number of crossings

2^{n}-2

equals

6,14,30

. The diagrams (a)+(c) are rotationally symmetric. All diagrams are monotone and convex.

General constructions of $n$ -Venn diagrams, valid for every $n\geq 1$ , were provided already by Venn [24] and much later by Edwards [7, 8]. In fact, these two constructions are connected via the well-known binary reflected Gray code, a listing of all $2^{n}$ binary strings of length $n$ such that any two consecutive strings differ in a single bit.

Particularly pleasing for the human eye are rotationally symmetric Venn diagrams, such as the ones in Figure 1 (a)+(c) and Figure 2 (a)+(e). They exist if and only if $n\geq 2$ is a prime number. The necessity of this condition was established by Henderson [13], and the sufficiency, i.e., a construction valid for all prime $n$ was shown by Griggs, Killian and Savage [10]. Their approach builds a symmetric chain partition in the so-called necklace poset. The problem to find simple symmetric $n$ -Venn diagrams is open in general. Solutions for small cases are only known for $n=1,3,5,7,11,13$ [16], and for general prime $n$ a construction is known that guarantees at least half of all crossings to be simple [15].

A $k$ -region in an $n$ -Venn diagram is a region that lies inside of exactly $k$ of the curves, and outside the remaining $n-k$ curves. A monotone diagram is one in which for every $0<k<n$ , every $k$ -region is adjacent to both a $(k-1)$ -region and a $(k+1)$ -region. A convex diagram is one in which every curve is convex. It is not hard to show that convex diagrams are monotone. Bultena, Grünbaum and Ruskey [3] also proved the converse, namely that every monotone diagram is isomorphic to a convex one. Thus, the combinatorial notion of monotonicity completely captures the geometric notion of convexity.

The number of non-isomorphic simple $n$ -Venn diagrams for $n=1,\ldots,6$ is $1,1,1,1,20,\allowbreak 3\,430\,404$ , and the number of monotone simple diagrams is $1,1,1,1,11,32\,255$ [2, 6, 12] (OEIS A386795 and A390247, respectively).

A well-known conjecture in the area, raised by Peter Winkler [26] in 1984 and reiterated in [27, 28], was that every simple $n$ -Venn diagram can be extended to a simple $(n+1)$ -Venn diagram by adding a suitable curve. Very recently, Winkler’s conjecture was disproved by Brenner, Kleist, Mütze, Rieck, and Verciani [2], who constructed counterexamples to the conjecture for all $n\geq 6$ . In particular, out of the $3\,430\,404$ many 6-Venn diagrams, 72 are not extendable to a 7-Venn diagram. Already earlier, Grünbaum [11] proposed a variant of Winkler’s conjecture, by dropping the requirement for the diagrams to be simple. Grünbaum’s conjecture was settled affirmatively by Chilakamarri, Hamburger and Pippert [5], using a classical theorem in graph theory of Whitney [25], later generalized by Tutte [23].

1.1 Maximizing and minimizing the number of crossings

Figure 2: Non-simple Venn diagrams for

n=3,4,5,6,7

that minimize the number of crossings. For those values of

n

, the number of crossings

L_{n}=\lceil\frac{2^{n}-2}{n-1}\rceil

equals

3,5,8,13,21

. Only in the diagrams (a) and (e) every crossing involves all

n

curves. The diagrams (a) and (e) are symmetric. The diagram (a) is monotone, while (b)–(e) are not monotone. None of the diagrams is convex, though (a) can be made convex by fixing the crossings and moving the centers of the circular arcs.

In this work, we are particularly interested in the number of crossings in an $n$ -Venn diagram. It is easy to see that simple $n$ -Venn diagrams have exactly $2^{n}-2$ many crossings, and this is the largest possible number of crossings among all $n$ -Venn diagrams. To complement this, Bultena and Ruskey [4] considered Venn diagrams with the smallest possible number of crossings. They proved that any $n$ -Venn diagram with $n\geq 2$ has at least

L_{n}\coloneq\left\lceil\frac{2^{n}-2}{n-1}\right\rceil

many crossings, and they called diagrams achieving this lower bound minimum Venn diagrams. If $(2^{n}-2)/(n-1)$ is integral, which happens for $n=2,3,7,19,43,55,127,163,\ldots$ (this is OEIS sequence A014741 incremented by 1), then this means that every crossing of the diagram involves all $n$ curves. So far, minimum Venn diagrams are only known for $n\leq 7$ ; see Figure 2. Bultena and Ruskey [4] conjectured that minimum $n$ -Venn diagrams exist for all $n\geq 8$ , and this is also mentioned as an open problem in Ruskey and Weston’s survey [19].

As a partial result, Bultena and Ruskey [4] proved that among monotone $n$ -Venn diagrams with $n\geq 2$ , the smallest possible number of crossings is $\binom{n}{\lfloor n/2\rfloor}$ , and this lower bound is achievable. Note that $\binom{n}{\lfloor n/2\rfloor}=\frac{2^{n}}{\sqrt{\pi n/2}}(1+o(1))$ , so this is still a $\Theta(\sqrt{n})$ -factor away from the general lower bound $L_{n}$ .

The problem of minimizing crossings in Venn diagrams can be seen as a variant of the well-known and heavily studied crossing number problem [9, 20], where one attempts to draw a graph in the plane with the goal of minimizing the number of edge crossings. Even for the complete graph $K_{n}$ or the hypercube $Q_{n}$ , this quantity is not known exactly.

1.2 Our results

Our first construction yields $n$ -Venn diagrams for the case when $n$ is a power of 2 in which the number of crossings is minimized up to a $(1+o(1))$ -factor (as $n\rightarrow\infty$ ).

Theorem 1.

There is an $8$ -Venn diagram with $40$ crossings, and for every $k\geq 4$ and $n\coloneq 2^{k}$ , there is an $n$ -Venn diagram with exactly

\left(1+\frac{33}{8n}-\frac{2}{2^{n/2}}-\frac{2n}{2^{n}}\right)\frac{2^{n}}{n}% \leq\left(1+\frac{33}{8n}\right)L_{n}=(1+o(1))L_{n}

many crossings.

The 8-Venn diagram with 40 crossings is shown in Figure 3.

Figure 3: An 8-Venn diagram with 40 crossings obtained from Theorem 1. The 8 curves are drawn with colors. Each black/white bubble represents one crossing that has to be contracted to a single point, where the open bubbles at the left and right boundary wrap around at the bottom.

For a general number of curves, i.e., when $n$ is not necessarily a power of 2, we apply a doubling construction to obtain an $n$ -Venn diagram in which the number of crossings is minimized up to a $(2+o(1))$ -factor.

Theorem 2.

For every $0\leq m\leq 7$ there is an $(8+m)$ -Venn diagram with $40\cdot 2^{m}$ crossings, and for every $k\geq 4$ , $n\coloneq 2^{k}$ and $0\leq m<n$ , there is an $(n+m)$ -Venn diagram with exactly

\left(1+\frac{33}{8n}-\frac{2}{2^{n/2}}-\frac{2n}{2^{n}}\right)\frac{2^{n+m}}{% n}\leq\left(1+\frac{33}{8n}\right)\frac{n+m}{n}L_{n+m}\leq(2+o(1))L_{n+m}

many crossings.

Figure 4 shows the approximation ratio guaranteed by Theorem 2 for all $8\leq n+m\leq 255$ .

Figure 4: Log-linear plot of the ratio

r

of the number of crossings of the Venn diagrams obtained from Theorem 2 and the lower bound.

In particular, Theorem 2 gives $n$ -Venn diagrams with the smallest known number of crossings for all $n\geq 8$ ; see Table 1.

Table 1: The number of crossings in the Venn diagrams obtained from Theorem 2 versus the lower bound, and the minimum numbers for monotone diagrams.

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
lower bound $L_{n}=\left\lceil\frac{2^{n}-2}{n-1}\right\rceil$ [4]	0	2	3	5	8	13	21	37	64	114	205	373	683	1261	2341	4369
Figure 2	0	2	3	5	8	13	21
Theorem 2								40	80	160	320	640	1280	2560	5120	5118
monotone $\binom{n}{\lfloor n/2\rfloor}$ [4]	0	2	3	6	10	20	35	70	126	252	462	924	1716	3432	6435	12870

1.3 Duals of Venn diagrams

Venn diagrams are conveniently studied by considering their dual graph; see Figure 5. Specifically, we consider the $n$ -dimensional hypercube $Q_{n}$ , or $n$ -cube for short, the graph formed by all subsets of $[n]\coloneq\{1,2,\ldots,n\}$ , with an edge between any two sets that differ in a single element. For an edge $e=\{x,x\cup\{i\}\}$ of $Q_{n}$ , we refer to $i$ as its direction.

The dual graph $Q(D)$ of an $n$ -Venn diagram $D$ satisfies the following properties:

①: It is a spanning subgraph of $Q_{n}$ , i.e., all $2^{n}$ vertices are present. Specifically, the vertex in $Q(D)$ corresponding to a region of the diagram $D$ is the set of all indices of curves that contain this region in their interior.
②: It is a plane graph, i.e., it is drawn in the plane without edge crossings, such that each face has even length $2\ell$ for some integer $2\leq\ell\leq n$ and contains exactly two edges of $\ell$ distinct directions. These $\ell$ directions correspond to the $\ell$ curves intersecting in the crossing corresponding to the face.
③: For every $j\in[n]$ , the two subgraphs of $Q(D)$ induced by all vertices $x$ with $j\in x$ , and with $j\notin x$ , respectively, are connected. This corresponds to the $j$ th curve being simple.

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

Figure 5: The dual of the 4-Venn diagram from Figure 2 (b) is a spanning subgraph of the 4-cube.

Clearly, the number of crossings of the diagram $D$ equals the number of faces of the dual graph $Q(D)$ . If $D$ is a minimum $n$ -Venn diagram, then almost all crossings involve all $n$ curves, i.e., in the dual graph $Q(D)$ , almost all faces have length $2n$ .

1.4 Proof ideas

Our proofs of Theorems 1 and 2 are constructive, and we proceed to give an informal sketch of the main steps of these constructions.

Using the characterization presented in the previous section, we build $n$ -Venn diagrams by constructing planar spanning subgraphs of the hypercube $Q_{n}$ satisfying conditions ①–③, with the goal of minimizing the number of faces.

For $n=2^{k}$ we start with a partition of $Q_{n}$ into isometric cycles of length $2n$ that is derived from a partition of $Q_{n-1}$ into isometric paths found by Ramras [18]. These cycles are translates of a single isometric cycle of length $2n$ by a certain linear subspace of $\mathbb{Z}_{2}^{n}$ of dimension $d\coloneq 2^{k}-k-1$ . For our construction we choose a slightly different basis of this space, denoted by $C_{k}$ , than originally used by Ramras.

In the first step of the construction, we embed the isometric cycles of the partition into the plane concentrically in an order that is specified by a certain Hamiltonian path $R$ of $Q_{d}$ (see Figure 9). Each vertex of $Q_{d}$ represents coefficients of a linear combination of the basis $C_{k}$ , so consecutive concentric cycles in this order differ only by one element of the basis $C_{k}$ . This guarantees that there are edges between consecutive cycles that create mainly large faces, but also some 6-faces. These edges between pairs of consecutive cycles are added in the second step.

In the last step, some cycle edges shared by 6-faces are removed to further reduce the total number of faces. For this purpose we specify a Hamiltonian path $R$ that contains long runs in its flip sequence. A run is a contiguous increasing or decreasing subsequence with increment or decrement 1, respectively. Interestingly, our construction of such long-run Hamiltonian cycles uses the same partition into isometric cycles as the aforementioned Venn diagram construction.

For values of $n$ that are not powers of 2, we use a straightforward doubling construction (see Lemma 10) to derive $n$ -Venn diagrams with relatively few crossings from the ones of the next smaller power of 2 constructed as described before. This is why the number of crossings increasingly deviates from the lower bound $L_{n}$ the farther the distance from the next smaller power of 2 gets, until the next larger power of 2 resets the process, which explains the behavior seen in Figure 4.

2 Isometric partitions of hypercubes

2.1 Preliminaries

Recall that $[n]=\{1,2,\ldots,n\}$ . We also define $2^{[n]}\coloneq\{x\mid x\subseteq[n]\}$ . For $x\subseteq[n]$ we write $\overline{x}\coloneq[n]\setminus x$ for the complement of $x$ w.r.t. the ground set $[n]$ . Given a vertex $x$ of $Q_{n}$ , we refer to $\overline{x}$ as the antipodal vertex of $x$ . For $x\subseteq[n]$ and an integer $k\geq 1$ we define $k\cdot x\coloneq\{ki\mid i\in x\}$ . All these operations thread in the natural way over sets and sequences. For example, for a set $X\subseteq 2^{[n]}$ and an integer $k\geq 1$ we have $k\cdot X=\{k\cdot x\mid x\in X\}$ .

For $x,y\subseteq[n]$ we define the symmetric difference as $x\oplus y\coloneq(x\setminus y)\cup(y\setminus x)$ . For any set $X\subseteq 2^{[n]}$ we define the span of $X$ by $\langle X\rangle\coloneq\{x_{1}\oplus x_{2}\oplus\cdots\oplus x_{t}\mid t\in\{% 0,\ldots,n\}\text{ and }x_{i}\in X$ for all $i\in[t]\}$ .

We refer to an edge $e=\{x,x\oplus\{i\}\}$ of direction $i$ in $Q_{n}$ as an $i$ -edge. The flip sequence of a path or cycle $P$ in $Q_{n}$ , denoted by $\sigma(P)$ , is the sequence of directions of edges along $P$ . We write $|\sigma(P)|$ for the length of this sequence. For example, the flip sequence of the path $P=(\{1,2\},\{1,2,3\},\{1,3\},\{3\},\{2,3\})$ in $Q_{3}$ is $\sigma(P)=(3,2,1,2)$ and we have $|\sigma(P)|=4$ .

A subgraph $H$ of a graph $G$ is isometric if it preserves distances, i.e., $d_{H}(u,v)=d_{G}(u,v)$ for any two vertices $u,v\in V(H)$ . In particular, a path in the hypercube $Q_{n}$ is isometric if and only if it contains no two edges of the same direction. A cycle in $Q_{n}$ is isometric if and only if the edges of the same direction come in pairs that lie oppositely on the cycle.

2.2 Partition into isometric paths

Ramras [18] described a partition of the hypercube $Q_{n-1}$ , for $n=2^{k}$ and $k\geq 1$ , into isometric paths. For this we consider the sequence of sets $(B_{k})_{k\geq 1}$ defined recursively by $B_{1}\coloneq\emptyset$ and

B_{k}\coloneq B_{k-1}\cup\{\{1,2^{k-1}+1\},\{2,2^{k-1}+2\},\ldots,\{2^{k-1}-1,% 2^{k}-1\}\}\text{ for }k\geq 2.

(1)

According to this definition, the first few sets are

\begin{split}B_{1}&=\emptyset,\qquad B_{2}=\{\{1,3\}\},\qquad B_{3}=\{\{1,3\},% \{1,5\},\{2,6\},\{3,7\}\},\\ B_{4}&=\{\{1,3\},\{1,5\},\{2,6\},\{3,7\},\{1,9\},\{2,10\},\{3,11\},\{4,12\},\{% 5,13\},\{6,14\},\{7,15\}\}.\end{split}

The sets in $B_{k}$ , viewed as binary (characteristic) vectors, are linearly independent and hence they form the basis of a linear subspace $\langle B_{k}\rangle$ of dimension $|B_{k}|=2^{k}-k-1$ of the space $\mathbb{Z}_{2}^{n}$ . For any $x\in\langle B_{k}\rangle$ , Ramras [18] defines a path $P(x)$ of length $n-1$ in $Q_{n-1}$ by

P(x)\coloneq(x,x\oplus\{1\},x\oplus\{1,2\},\ldots,x\oplus\{1,2,\ldots,n-1\}).

(2)

The flip sequence along this path is $\sigma(P)=(1,2,\ldots,n-1)$ , and the end vertices of $P(x)$ are antipodal in $Q_{n-1}$ , i.e., the last vertex $x\oplus\{1,2,\ldots,n-1\}$ is the complement of the first vertex $x$ w.r.t. the ground set $[n-1]$ . The following theorem is illustrated on the left hand side of Figure 6.

Theorem 3 ([18, Thm. 2.5]).

For any $k\geq 1$ and $n\coloneq 2^{k}$ , the isometric paths $P(x)$ of length $n-1$ defined in (2) for all $x\in\langle B_{k}\rangle$ form a partition of the vertex set of $Q_{n-1}$ .

Figure 6: Illustration of Theorem 3 (left) and Corollary 5 (right) for the case

k=2

. The bottom right shows a schematic illustration of the cycles showing only the starting vertices on the left and the flip sequences along each cycle.

2.3 Finding another basis for $\langle B_{k}\rangle$

For our purposes, we choose a different basis of the subspace $\langle B_{k}\rangle$ , namely one that contains a larger number of $2$ -sets $\{a,b\}$ with $|b-a|=2$ . We define

\begin{split}C_{1}&\coloneq O_{1}\coloneq\emptyset,\\ O_{k}&\coloneq\{\{1,3\},\{3,5\},\ldots,\{2^{k}-3,2^{k}-1\}\}\text{ for $k\geq 2% $, and}\\ C_{k}&\coloneq O_{k}\cup 2C_{k-1}\text{ for }k\geq 2.\end{split}

(3)

According to this definition, the first few sets are

\begin{split}O_{1}&=\emptyset,\qquad O_{2}=\{\{1,3\}\},\qquad O_{3}=\{\{1,3\},% \{3,5\},\{5,7\}\},\\ O_{4}&=\{\{1,3\},\{3,5\},\{5,7\},\{7,9\},\{9,11\},\{11,13\},\{13,15\}\},\end{split}

and

\begin{split}C_{1}&=\emptyset,\qquad C_{2}=\{\{1,3\}\},\qquad C_{3}=\{\{1,3\},% \{3,5\},\{5,7\},\{2,6\}\},\\ C_{4}&=\{\{1,3\},\{3,5\},\{5,7\},\{7,9\},\{9,11\},\{11,13\},\{13,15\},\{2,6\},% \{6,10\},\{10,14\},\{4,12\}\}.\end{split}

Note that $|b-a|=2$ for every $\{a,b\}\in O_{k}$ and furthermore, $|O_{k}|=2^{k-1}-1$ and $|C_{k}|=2^{k}-k-1$ .

Lemma 4.

The sets $B_{k}$ and $C_{k}$ defined in (1) and (3), respectively, satisfy $\langle B_{k}\rangle=\langle C_{k}\rangle$ for any $k\geq 1$ .

The proof of Lemma 4 can be found in the preprint [1].

2.4 Partition into isometric cycles

From Theorem 3 it follows that for $n=2^{k}$

C(x)\coloneq(P(x),\overline{P(x)}\cup\{n\})

(4)

is an isometric cycle of length $2n$ in $Q_{n}$ , with flip sequence $\sigma(C(x))=(1,2,\ldots,n,1,2,\ldots,n)$ , and furthermore, the cycles $C(x)$ for all $x\in\langle B_{k}\rangle$ form a partition of the vertex set of $Q_{n}$ . Combining this with Lemma 4 we obtain the following isometric partition into cycles, which is the starting point of our constructions later on; see the right hand side of Figure 6.

Corollary 5.

For any $k\geq 1$ and $n\coloneq 2^{k}$ , the isometric cycles $C(x)$ of length $2n$ defined in (4) for all $x\in\langle C_{k}\rangle$ form a partition of the vertex set of $Q_{n}$ .

The following lemma describes the edges between the cycles $C(x)$ , and it is illustrated in Figure 7. The proof is elementary, and we omit it.

Figure 7: Illustration of Lemma 6 and definitions of the edge sets

E(x,\{a,b\})

,

F(x,\{a,b\})

,

E_{\diagdown}(x,a)

, and

E_{\diagup}(x,a)

.

Lemma 6.

Let $k\geq 2$ and $n\coloneq 2^{k}$ , and let $x,y\in\langle C_{k}\rangle$ be such that $y=x\oplus\{a,b\}$ with $a<b$ . Then the cycles $C(x)$ and $C(y)$ have the following edges between them in $Q_{n}$ :

(i)

From the start/end vertex of each of the two $a$ -edges of $C(x)$ , there is a $b$ -edge to the end/start vertex of the corresponding $a$ -edge of $C(y)$ .
(ii)

From the start/end vertex of each of the two $b$ -edges of $C(x)$ , there is an $a$ -edge to the end/start vertex of the corresponding $b$ -edge of $C(y)$ .

If $b=a+2$ , then in addition the following edges are present:

(iii)

From the start/end vertex of each of the two $a$ -/ $(a+2)$ -edges of $C(x)$ , there is an $(a+1)$ -edge to the end/start vertex of the corresponding $(a+2)$ -/ $a$ -edge of $C(y)$ .

For $b>a+2$ we write $E(x,\{a,b\})$ for the set of four edges shown in Figure 7 (a1). Furthermore, for $b=a+2$ we write $E_{\diagdown}(x,a)$ and $E_{\diagup}(x,a)$ for the two sets of three edges shown in parts (b1) and (b2) of the figure, respectively. Lastly, we write $F(x,\{a,b\})$ for the 4-cycle shown in part (a2) of the figure.

3 Long-run Gray code construction

Given a path or cycle $P$ in $Q_{n}$ and integer $\rho\in[n]$ , an increasing or decreasing $\rho$ -run in its flip sequence $\sigma(P)$ is a contiguous subsequence $(a,a+1,a+2,\ldots,a+\ell)$ or $(a+\ell,a+\ell-1,\ldots,a+1,a)$ such that $a+\ell\leq\rho$ . In words, it is a sequence of values that are increasing or decreasing (with increment 1 or decrement 1, respectively) such that all flipped directions are at most $\rho$ . The parameter $\ell\geq 0$ , which is one less than the length of the subsequence, is called the length of the run.

A $\rho$ -run is maximal if it cannot be extended, i.e., if it is not contained in another $\rho$ -run. Note that two maximal $\rho$ -runs may overlap in at most one element, namely the last element of an increasing run and the first element of a decreasing run, or vice versa. Furthermore, note that a maximal $\rho$ -run of length 0 does not overlap with any other $\rho$ -runs, and a maximal $\rho$ -run of length 1 does not overlap with two other $\rho$ -runs in the first and last element, as this would create a flip sequence $a+1,a,a+1,a$ or $a,a+1,a,a+1$ , i.e., a 4-cycle, which is impossible. A $\rho$ -run partition of $\sigma(P)$ is obtained by considering all maximal $\rho$ -runs in $\sigma(P)$ , and removing, from every pair of consecutive overlapping runs, the element in which they overlap from one of the two runs. For example, the flip sequence $\sigma(P)=(3,1,2,3,2,1,2,4,3,2,4)$ has the maximal 3-runs $(\overbracket{3},\hbox to0.0pt{$\displaystyle\overbracket{\phantom{1,2,3}}$% \hss}1,2,\hbox to0.0pt{$\displaystyle\underbracket{\phantom{3,2,1}}$\hss}3,2,% \hbox to0.0pt{$\displaystyle\overbracket{\phantom{1,2}}$\hss}1,2,\bcancel{4},% \underbracket{3,2},\bcancel{4}),$ where increasing and decreasing runs are marked by overbrackets and underbrackets, respectively, and the cancelled elements are not contained in any 3-run. Thus we obtain $(\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,2\!$}},\framebox{\raisebox{0.0pt}[% 5.39996pt][0.60004pt]{$\!3,2,1\!$}},\framebox{\raisebox{0.0pt}[5.39996pt][0.60% 004pt]{$\!2\!$}},\bcancel{4},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{% $\!3,2\!$}},\bcancel{4})$ as a 3-run partition of $\sigma(P)$ , where the boxes indicate the runs. Similarly, $(\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,2,3\!$}},\framebox{\raisebox{0.0pt% }[5.39996pt][0.60004pt]{$\!2,1\!$}},\framebox{\raisebox{0.0pt}[5.39996pt][0.60% 004pt]{$\!2\!$}},\bcancel{4},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{% $\!3,2\!$}},\bcancel{4})$ , $(\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,2\!$}},\framebox{\raisebox{0.0pt}[% 5.39996pt][0.60004pt]{$\!3,2\!$}},\framebox{\raisebox{0.0pt}[5.39996pt][0.6000% 4pt]{$\!1,2\!$}},\bcancel{4},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{% $\!3,2\!$}},\bcancel{4})$ and $(\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,2,3\!$}},\framebox{\raisebox{0.0pt% }[5.39996pt][0.60004pt]{$\!2\!$}},\framebox{\raisebox{0.0pt}[5.39996pt][0.6000% 4pt]{$\!1,2\!$}},\bcancel{4},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{% $\!3,2\!$}},\bcancel{4})$ are also valid 3-run partitions.

Although there may be different $\rho$ -run partitions, their number and total length, i.e., sum of lengths of all runs, is the same, and we denote these quantities by $\nu_{\rho}(P)$ and $\lambda_{\rho}(P)$ . Note that the number of entries of $\sigma(P)$ exceeding $\rho$ equals $|\sigma(P)|-\nu_{\rho}(P)-\lambda_{\rho}(P)$ . In the example from before we have $\nu_{3}(P)=5$ and $\lambda_{3}(P)=4$ .

Our first aim is to find a Hamiltonian path $P$ in the hypercube $Q_{n}$ for $n=2^{k}$ for which the quantity $\nu_{n-1}(P)+2\lambda_{n-1}(P)$ is as large as possible, i.e., we want to maximize the number of flipped directions contained in long $(n-1)$ -runs. We shall see that maximizing this quantity corresponds to minimizing the number of crossings in the Venn diagrams constructed in the next section (see Lemma 9).

Lemma 7.

Let $k\geq 2$ and $n\coloneq 2^{k}$ . There is a Hamiltonian path $P$ in $Q_{n}$ that satisfies

\nu_{n-1}(P)=\begin{cases}6&\text{if }k=2,\\ \frac{17}{8}\cdot\frac{2^{n}}{n}-4&\text{if }k\geq 3,\end{cases}\text{ and }% \lambda_{n-1}(P)=\begin{cases}8&\text{if }k=2,\\ 2^{n}-\frac{25}{8}\cdot\frac{2^{n}}{n}+4&\text{if }k\geq 3.\end{cases}

Proof.

For $k=2$ we take the Hamiltonian path $P$ with $\sigma(P)=(\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,2,3\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!2\!$}},\framebox{\raisebox% {0.0pt}[5.39996pt][0.60004pt]{$\!1,2,3\!$}},\bcancel{4},\framebox{\raisebox{0.% 0pt}[5.39996pt][0.60004pt]{$\!3,2,1\!$}},\allowbreak\framebox{\raisebox{0.0pt}% [5.39996pt][0.60004pt]{$\!2\!$}},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004% pt]{$\!3,2,1\!$}})$ , proving that $\nu_{3}(P)=6$ and $\lambda_{3}(P)=8$ ; see the top part of Figure 8.

Figure 8: Illustration of the proof of Lemma 7. The edges that are removed while taking the symmetric difference are dashed, including the wrap-around edge of the first cycle. The subsequences highlighted in gray are

(n-1)

-runs.

For $k\geq 3$ we construct a Hamiltonian path $P$ in $Q_{n}$ as follows; see the bottom part of Figure 8. We start with the partition of $Q_{n}$ into cycles given by Corollary 5. Formally, we define the cycle factor ${\mathcal{C}}\coloneq\bigcup_{x\in\langle C_{k}\rangle}C(x)$ . Each of the cycles of ${\mathcal{C}}$ has length $2n$ and the total number of cycles is $2^{n}/(2n)=2^{2^{k}}/2^{k+1}=2^{2^{k}-k-1}=2^{d}$ for $d\coloneq 2^{k}-k-1$ . Recall that $|C_{k}|=2^{k}-k-1=d$ .

Let $(c_{1},\ldots,c_{d})$ be a sequence obtained by sorting all elements of the set $C_{k}$ such that $c_{1}=\{1,3\},c_{2}=\{3,5\},c_{3}=\{2,6\}$ , and the remaining elements appear in arbitrary order. We take a Hamiltonian path $R$ in $Q_{d}$ whose flip sequence $\sigma(R)\eqcolon(s_{1},\ldots,s_{2^{d}-1})$ alternates copies of the subsequence $S\coloneq(1,2,1,3,1,2,1)$ with single flips $s_{8i}\geq 4$ for $i\geq 1$ , starting with $S$ , i.e., $\sigma(R)=(S,s_{8},S,s_{16},S,s_{24},\ldots,S,s_{2^{d}-8},S)$ . For example, we may take for $R$ the well-known binary reflected Gray code in $Q_{d}$ . Note that $\sigma(R)$ contains exactly $2^{d-3}$ copies of $S$ . We define an ordering $x_{1},\ldots,x_{2^{d}}$ of all elements of $\langle C_{k}\rangle$ recursively by $x_{1}\coloneq\emptyset$ and $x_{i+1}\coloneq x_{i}\oplus c_{s_{i}}$ for $i=1,\ldots,2^{d}-1$ . Note that this definition is valid since each element of $\langle C_{k}\rangle$ is a linear combination of the basis $C_{k}$ , and $R$ visits all $d$ -tuples of $\{0,1\}$ -coefficients.

Consider the symmetric difference of the edge sets of the cycle factor ${\mathcal{C}}$ with all 4-cycles $F(x_{i},c_{s_{i}})$ for $i=1,\ldots,2^{d}-1$ . Each of the 4-cycles has a pair of opposite edges in common with two consecutive cycles from the factor, and thus glues them together to a single cycle. Therefore, the resulting set of edges is a Hamiltonian cycle in $Q_{n}$ . Removing one of its $n$ -edges gives a Hamiltonian path $P$ in $Q_{n}$ . Note that the 4-cycles $F(x_{i},c_{s_{i}})$ and $F(x_{i+1},c_{s_{i+1}})$ are edge-disjoint for $i=1,\ldots,2^{d}-2$ .

In the remainder of the proof we compute the quantities $\nu_{n-1}(P)$ and $\lambda_{n-1}(P)$ . Recall from (2) and (4) that for each cycle $C(x_{i})$ , $i=1,\ldots,2^{d}$ , the flip sequence is $\sigma(C(x_{i}))=(1,2,\ldots,n,1,2,\ldots,n)$ , i.e., it has two maximal $(n-1)$ -runs of length $n-2$ each. Observe from Figure 8 that when gluing together the eight cycles $C(x_{i})$ for which $s_{i}\in\{1,2,3\}$ belongs to a copy of $S$ in $\sigma(R)$ , the flip sequence of the resulting cycle has the $(n-1)$ -run partition

	$\displaystyle\!\!\!\big(\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3,% 2\!$}},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!5\!$}},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!4,\dots,n-1\!$}},\bcancel{n},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},\bcancel{% n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!6\!$}},\framebox{\raisebox% {0.0pt}[5.39996pt][0.60004pt]{$\!3,\dots,n-1\!$}},\bcancel{n},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},\bcancel{n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3,2\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!5\!$}},\framebox{\raisebox% {0.0pt}[5.39996pt][0.60004pt]{$\!4,\dots,n-1\!$}},\bcancel{n},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},\bcancel{n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!2,\dots,n-1\!$}},\bcancel{% n},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},% \bcancel{n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3,2\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!5\!$}},\framebox{\raisebox% {0.0pt}[5.39996pt][0.60004pt]{$\!4,\dots,n-1\!$}},\bcancel{n},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},\bcancel{n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!6\!$}},\framebox{\raisebox% {0.0pt}[5.39996pt][0.60004pt]{$\!3,\dots,n-1\!$}},\bcancel{n},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},\bcancel{n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3,2\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!5\!$}},\framebox{\raisebox% {0.0pt}[5.39996pt][0.60004pt]{$\!4,\dots,n-1\!$}},\bcancel{n},\framebox{% \raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},\bcancel{n},$
	$\displaystyle\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!3\!$}},% \framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!2,\dots,n-1\!$}},\bcancel{% n},\framebox{\raisebox{0.0pt}[5.39996pt][0.60004pt]{$\!1,\dots,n-1\!$}},% \bcancel{n}\big),$

consisting of 30 runs of total length $16n-46$ .

When taking the symmetric difference with the $2^{d-3}-1$ remaining 4-cycles $F(x_{i},c_{s_{i}})$ with $s_{i}\geq 4$ , then inserting each such 4-cycle splits two runs $\!2,\dots,n-1\!$ into two times two runs $\!2,\dots,a-1\!$ , $\!a+1,\dots,n-1\!$ and two trivial runs $\!b\!$ , where $\{a,b\}\coloneq c_{s_{i}}$ such that $a<b$ , i.e., the number of runs increases by 4 and the total length decreases by 4.

Lastly, note that removing one $n$ -edge from the resulting Hamiltonian cycle to break it into the Hamiltonian path $P$ does not change any $(n-1)$ -runs.

Combining these observations, we obtain

\begin{split}\nu_{n-1}(P)&=30\cdot 2^{d-3}+4\cdot(2^{d-3}-1)=\frac{17}{8}\cdot% \frac{2^{n}}{n}-4\;\;\text{ and }\\ \lambda_{n-1}(P)&=(16n-46)\cdot 2^{d-3}-4\cdot(2^{d-3}-1)=2^{n}-\frac{25}{8}% \cdot\frac{2^{n}}{n}+4,\end{split}

where we used the relation $2^{d}=\frac{2^{n}}{2n}$ . $\hfill\blacktriangleleft$

For a general dimension that is not necessarily a power of 2 we generalize the result from before by applying a straightforward product construction.

Corollary 8.

Let $k\geq 2$ , $n\coloneq 2^{k}$ , and $0\leq m<n$ . There is a Hamiltonian path $P$ in $Q_{n+m}$ that satisfies

\nu_{n-1}(P)=\begin{cases}6\cdot 2^{m}&\text{if }k=2,\\ 2^{m}\big(\frac{17}{8}\cdot\frac{2^{n}}{n}-4\big)&\text{if }k\geq 3,\end{cases% }\text{ and }\lambda_{n-1}(P)=\begin{cases}8\cdot 2^{m}&\text{if }k=2,\\ 2^{m}\big(2^{n}-\frac{25}{8}\cdot\frac{2^{n}}{n}+4\big)&\text{if }k\geq 3.\end% {cases}

Proof.

We use the fact that $Q_{n+m}$ is isomorphic to the Cartesian product $Q_{n}\mathbin{\square}Q_{m}$ . Consequently, if $P$ is a Hamiltonian path in $Q_{n}$ and $R$ is a Hamiltonian path in $Q_{m}$ with flip sequence $\sigma(R)\eqcolon(s_{1},\dots,s_{2^{m}-1})$ , then $Q_{n+m}$ has a Hamiltonian path $P^{\prime}$ with flip sequence

\sigma(P^{\prime})=\big(\sigma(P),s_{1}+n,\operatorname{rev}(\sigma(P)),s_{2}+% n,\sigma(P),\ldots,s_{2^{m}-2}+n,\sigma(P),s_{2^{m}-1}+n,\operatorname{rev}(% \sigma(P))\big),

where $\operatorname{rev}(\sigma(P))$ denotes the reverse of the sequence $\sigma(P)$ . By taking the Hamiltonian path $P$ in $Q_{n}$ given by Lemma 7 and any Hamiltonian path $R$ in $Q_{m}$ , the lemma follows. $\hfill\blacktriangleleft$

Note that as $n\rightarrow\infty$ , we have $\lambda_{n-1}(P)=(1-o(1))2^{n+m}$ , i.e., almost all flips along the Hamiltonian path $P$ belong to an $(n-1)$ -run.

4 Proof of Theorem 1

In this section, we describe our constructions of almost-minimum $n$ -Venn diagrams for the case where $n$ is a power of 2, thus proving Theorem 1.

Lemma 9.

Let $k\geq 3$ , $n\coloneq 2^{k}$ , $d\coloneq 2^{k}-k-1$ , and $\rho\coloneq 2^{k-1}-1=n/2-1$ , and let $P$ be a Hamiltonian path in $Q_{d}$ . Then there is an $n$ -Venn diagram with exactly $2\cdot\frac{2^{n}}{n}-\nu_{\rho}(P)-2\lambda_{\rho}(P)-2$ many crossings.

Proof.

To prove the lemma, we construct a plane subgraph $H\subseteq Q_{n}$ satisfying properties ①–③ stated in Section 1.3 that has exactly $2\cdot\frac{2^{n}}{n}-\nu_{\rho}(P)-2\lambda_{\rho}(P)-2$ many faces, as follows. We start with the partition of $Q_{n}$ into cycles given by Corollary 5. Formally, we define the cycle factor ${\mathcal{C}}\coloneq\bigcup_{x\in\langle C_{k}\rangle}C(x)$ . Each of the cycles of ${\mathcal{C}}$ has length $2n$ and the total number of cycles is $2^{n}/(2n)=2^{2^{k}}/2^{k+1}=2^{2^{k}-k-1}=2^{d}$ . Recall that $|C_{k}|=2^{k}-k-1=d$ .

Let $c=(c_{1},\ldots,c_{d})$ be a sequence obtained by sorting all elements of the set $C_{k}$ such that all 2-sets from $O_{k}\subseteq C_{k}$ appear first and with increasing minimum values, and the remaining 2-sets appear afterwards in arbitrary order. That is, we choose the first $\rho$ elements as $(c_{1},\dots,c_{\rho})=(\{1,3\},\{3,5\},\ldots,\{2^{k}-3,2^{k}-1\})$ , which is the order from (3), or equivalently, $c_{i}=\{2i-1,2i+1\}$ for $1\leq i\leq\rho$ . Recall that $|O_{k}|=2^{k-1}-1=\rho\leq d$ .

Figure 9: Illustration of the proof of Lemma 9 for the case

k=3

, i.e.,

n=8

. The dashed edges are deleted, so they are not part of

H

. The constructed dual graph

H

of an 8-Venn diagram has 40 faces, i.e., the corresponding Venn diagram has 40 crossings; see Figure 3, only 3 more than the lower bound

L_{8}=37

. All faces except the red ones have maximum possible length

2n

.

We consider the flip sequence $\sigma(P)\eqcolon(s_{1},\ldots,s_{2^{d}-1})$ of the given Hamiltonian path $P$ in $Q_{d}$ . The $\rho$ -runs in this sequence will be particularly relevant for our construction. We define an ordering $x_{1},\ldots,x_{2^{d}}$ of all elements of $\langle C_{k}\rangle$ recursively by $x_{1}\coloneq\emptyset$ and $x_{i+1}\coloneq x_{i}\oplus c_{s_{i}}$ for $i=1,\ldots,2^{d}-1$ . Note that this definition is valid since each element of $\langle C_{k}\rangle$ is a linear combination of the basis $C_{k}$ , and $P$ visits all $d$ -tuples of $\{0,1\}$ -coefficients.

To construct $H$ , we first embed the cycles of the factor ${\mathcal{C}}$ in the plane by nesting them concentrically according to this ordering, i.e., $C(x_{1})$ is the outermost cycle, and for $i=1,\ldots,2^{d}-1$ , the cycle $C(x_{i+1})$ is nested concentrically inside $C(x_{i})$ .

Next, we add edges between every pair of consecutive cycles $C(x_{i})$ and $C(x_{i+1})$ for $i=1,\ldots,2^{d}-1$ according to the following rules; see Figure 9. We first fix a $\rho$ -run partition of $P$ throughout, so whenever we refer to a $\rho$ -run in the following, we mean a run in this fixed partition. If $s_{i}\leq\rho$ , then we have $c_{s_{i}}=\{a,a+2\}$ for $a\coloneq 2s_{i}-1$ . If the entry $s_{i}$ of $\sigma(P)$ is contained in an increasing $\rho$ -run, then we add the three edges of $E_{\diagdown}(x_{i},a)$ , and if it is contained in a decreasing $\rho$ -run, then we add the three edges of $E_{\diagup}(x_{i},a)$ instead. If the run has length 0, i.e., it consists only of a single entry, we treat it as one of the two cases, say, increasing. On the other hand, if $s_{i}>\rho$ , then we add the four edges of $E(x_{i},c_{s_{i}})$ .

In this way, we obtain an intermediate connected plane graph with $C(x_{1})$ as the outer face and $C(x_{2^{d}})$ as the innermost face that has either 3 or 4 faces between cycles $C(x_{i})$ and $C(x_{i+1})$ for $i=1,\dots,2^{d}-1$ , namely if $s_{i}\leq\rho$ or $s_{i}>\rho$ holds, respectively. Since the number of entries $s_{i}$ in $\sigma(P)$ with $s_{i}\leq\rho$ is exactly $\nu_{\rho}(P)+\lambda_{\rho}(P)$ , the number of faces of the intermediate graph is exactly

2+4(2^{d}-1)-(\nu_{\rho}(P)+\lambda_{\rho}(P))=2\cdot\frac{2^{n}}{n}-\nu_{\rho% }(P)-\lambda_{\rho}(P)-2.

In the last step of constructing $H$ , we remove edges from some of the cycles $C(x_{i})$ , $i=2,\ldots,2^{d}-1$ , according to the following rules: If $s_{i-1}$ and $s_{i}$ belong to the same increasing $\rho$ -run in $\sigma(P)$ , then we have $c_{s_{i-1}}=\{a-2,a\}$ and $c_{s_{i}}=\{a,a+2\}$ for $a\coloneq 2s_{i}-1$ , and then we remove the first $a$ -edge of $C(x_{i})$ . If $s_{i-1}$ and $s_{i}$ belong to the same decreasing $\rho$ -run in $\sigma(P)$ , then we have $c_{s_{i-1}}=\{a,a+2\}$ and $c_{s_{i}}=\{a-2,a\}$ for $a\coloneq 2s_{i}+1$ , and then we remove the first $a$ -edge of $C(x_{i})$ . This completes the description of how to construct the subgraph $H$ of $Q_{n}$ .

Note that each removed edge decreases the number of faces by 1. Since the number of removed edges is exactly $\lambda_{\rho}(P)$ , the number of faces of $H$ is exactly

2\cdot\frac{2^{n}}{n}-\nu_{\rho}(P)-2\lambda_{\rho}(P)-2,

as claimed. It remains to check that the graph $H\subseteq Q_{n}$ just defined satisfies conditions ①–③.

Condition ① holds since the cycles $C(x_{i})$ for $i=1,\dots,2^{d}$ form a partition of $Q_{n}$ by Corollary 5. To verify condition ②, first observe in Figure 7 (a1), (b1) and (b2) that no two edges from any of the sets $E(x,\{a,b\})$ , $E_{\diagdown}(x,a)$ , or $E_{\diagup}(x,a)$ are crossing and thus $H$ is a plane graph. Furthermore, observe from Figure 7 (a1) that the four facial cycles between two cycles obtained by adding the edge set $E(x,\{a,b\})$ have lengths $2(b-a)+2$ and $2(n-(b-a))+2$ and flip sequences

	$\displaystyle(a,a+1,\ldots,b-1,a,b,b-1,\dots,a+1,b),\text{ and}$
	$\displaystyle(b,b+1,\ldots,n,1,2,\dots,a-1,b,a,a-1,\ldots,1,n,n-1,\dots,b+1,a),$

respectively. Similarly, observe from Figures 7 (b1) and (b2) that the three facial cycles between two cycles obtained by adding the edge set $E_{\diagdown}(x,a)$ or $E_{\diagup}(x,a)$ have lengths 6, $2n$ , and $2n$ and flip sequences

	$\displaystyle(a,a+1,a,a+2,a+1,a+2),$
	$\displaystyle(a+2,a+3,\ldots,n,1,2,\ldots,a-1,a+1,a+2,a+1,\dots,1,n,n-1,\ldots% ,a+3,a),\text{ and}$
	$\displaystyle(a,a+1,\ldots,n,1,2,\ldots,a-1,a+2,a,a-1,\ldots,1,n,n-1,\dots,a+3% ,a+1),$

respectively. It can be checked directly that the aforementioned faces, as well as the outer face $C(x_{1})$ and the innermost face $C(x_{2^{d}})$ satisfy condition ②.

In the last step of the construction we removed some edges from the cycles $C(x_{i})$ . Specifically, for each increasing or decreasing run of length $\ell\geq 2$ , we glue together $\ell$ adjacent 6-cycles, creating a new facial cycle of length $4\ell+2$ . Observe that the adjacent 6-faces have edge directions shifted by 2 and therefore their directions overlap only in the largest resp. smallest direction, and the shared direction is the direction of the edge that was removed. It follows that the resulting cycles of length $4\ell+2$ also satisfy condition ②.

To prove condition ③ we establish by induction on $i=1,\dots,2^{d}$ that for every direction $j\in[n]$ every vertex $x$ of $C(x_{i})$ is connected in $H$ to either the vertex $\emptyset$ or $[n]$ along a path that avoids any $j$ -edges. Specifically, $x$ is connected to $\emptyset$ if $j\notin x$ and to $[n]$ if $j\in x$ .

To settle the induction basis $i=1$ , recall that the flip sequence of $C(x_{1})$ is $\sigma(C(x_{1}))=(1,2,\ldots,n,1,2,\ldots,n)$ , so removing any two $j$ -edges for some $j\in[n]$ from $C(x_{1})$ results in two antipodal paths of length $n-1$ , respectively containing vertex $\emptyset$ and vertex $[n]$ .

For the induction step $i\rightarrow i+1$ , it suffices to show that every vertex of $C(x_{i+1})$ is connected in $H$ to some vertex of $C(x_{i})$ along a path that has no $j$ -edges. We distinguish two cases according to which edges were added between $C(x_{i})$ and $C(x_{i+1})$ .

In the case when the four edges of $E(x_{i},c_{s_{i}})$ , $c_{s_{i}}\eqcolon\{a,b\}$ , were added between $C(x_{i})$ and $C(x_{i+1})$ , observe that the two added $a$ -edges are incident to antipodal vertices of $C(x_{i+1})$ , and the same is true for the two added $b$ -edges. Hence removing any two $j$ -edges, where $j\in[n]$ , from $C(x_{i+1})$ results in two subpaths that are both connected to $C(x_{i})$ along an edge of $E(x_{i},c_{s_{i}})$ that is not a $j$ -edge, even if $j\in\{a,b\}$ .

Figure 10: Verification of condition ③ in the proof of Lemma 9.

Now we consider the case when the three edges of $E_{\diagdown}(x_{i},a)$ were added between $C(x_{i})$ and $C(x_{i+1})$ (i.e., we have $b=a+2$ ). The third case when the edges of $E_{\diagup}(x_{i},a)$ were added is analogous. We will also assume w.l.o.g. that the first $(a+2)$ -edge on $C(x_{i+1})$ was removed; otherwise the situation is even simpler; see Figure 10. We denote the removed $(a+2)$ -edge by $\{u,v\}$ . If $j\notin\{a,a+1,a+2\}$ , then removing the $j$ -edges from $C(x_{i+1})$ results in three subpaths that are all connected to $C(x_{i})$ , each path along an edge of $E_{\diagdown}(x_{i},a)$ . If $j=a+2$ , then removing also the second $(a+2)$ -edge from $C(x_{i+1})$ results in two subpaths of $C(x_{i+1})$ that are both connected to $C(x_{i})$ , since the added edges of directions $a$ and $a+1$ are incident to antipodal vertices of $C(x_{i+1})$ . For the last case $j\in\{a,a+1\}$ recall that there is a path $R$ between $u$ and $v$ along the face of $H$ containing these two vertices and vertices of $C(x_{i+j})$ for $j\geq 2$ , and the path $R$ does not contain edges of directions $a$ or $a+1$ . The path $R$ and the two edges of $E_{\diagdown}(x_{i},a)$ that are not of direction $j$ connect all vertices of $C(x_{i+1})$ to $C(x_{i})$ along a path not containing any $j$ -edges. This shows that the graph $H$ indeed satisfies condition ③. $\hfill\blacktriangleleft$

With Lemma 9 in hand, we are now in position to prove Theorem 1.

Proof of Theorem 1.

For $k\geq 3$ we define $n\coloneq 2^{k}$ , $d\coloneq 2^{k}-k-1$ and $\rho\coloneq 2^{k-1}-1=n/2-1$ .

If $k=3$ , we have $n=8$ , $d=4$ and $\rho=3$ . We apply Lemma 7 for $\hat{k}\coloneq k-1=2$ , $\hat{n}\coloneq 2^{\hat{k}}=4$ to obtain a Hamiltonian path $P$ in $Q_{4}$ with $\nu_{3}(P)=6$ and $\lambda_{3}(P)=8$ . Therefore, Lemma 9 yields an $8$ -Venn diagram with exactly $2\cdot\frac{2^{8}}{8}-6-2\cdot 8-2=40$ crossings; see Figures 3 and 9.

If $k\geq 4$ , we apply Corollary 8 for $\hat{k}\coloneq k-1$ , $\hat{n}\coloneq 2^{\hat{k}}=2^{k-1}=n/2$ and $\hat{m}\coloneq d-\hat{n}=2^{k-1}-k-1$ to obtain a Hamiltonian path $P$ in $Q_{\hat{n}+\hat{m}}=Q_{d}$ with

	$\displaystyle\nu_{\rho}(P)$	$\displaystyle=\nu_{\hat{n}-1}(P)=\left(\frac{17}{8}\cdot\frac{2^{\hat{n}}}{% \hat{n}}-4\right)2^{\hat{m}}=\frac{17}{8}\cdot\frac{2^{n}}{n^{2}}-\frac{2^{n/2% }}{n/2}\quad\text{and}$
	$\displaystyle\lambda_{\rho}(P)$	$\displaystyle=\lambda_{\hat{n}-1}(P)=\left(2^{\hat{n}}-\frac{25}{8}\cdot\frac{% 2^{\hat{n}}}{\hat{n}}+4\right)2^{\hat{m}}=\frac{2^{n}}{2n}-\frac{25}{8}\cdot% \frac{2^{n}}{n^{2}}+\frac{2^{n/2}}{n/2}.$

Therefore, Lemma 9 yields an $n$ -Venn diagram with exactly

2\cdot\frac{2^{n}}{n}-\nu_{\rho}(P)-2\lambda_{\rho}(P)-2=\left(1+\frac{33}{8n}% -\frac{2}{2^{n/2}}-\frac{2n}{2^{n}}\right)\frac{2^{n}}{n}

many crossings.

Finally, note that the inequality $\frac{2^{n}}{n}\leq L_{n}=\lceil\frac{2^{n}-2}{n-1}\rceil$ holds for all $n\geq 2$ . $\hfill\blacktriangleleft$

5 Proof of Theorem 2

We now show how to lift the construction of $n$ -Venn diagrams for the case when $n$ is a power of 2 to the general case, thus proving Theorem 2. The lifting is achieved via the following straightforward doubling construction.

We say that a face of the dual graph of an $n$ -Venn diagram is colorful if it has length $2n$ and contains two antipodal vertices of $Q_{n}$ . In the primal Venn diagram, such a face corresponds to a crossing involving all $n$ curves for which the cyclic ordering of curves around the crossing can be split into two halves such that every curve appears exactly once in each half. Consequently, there is a way to draw an additional curve through this crossing that crosses (not only intersects) each of the $n$ existing curves.

Lemma 10.

If there is an $n$ -Venn diagram $D$ whose dual graph has a colorful face, then there is an $(n+1)$ -Venn diagram whose dual graph has a colorful face and with twice as many crossings as $D$ .

The proof of Lemma 10 can be found in the preprint [1]. With Lemma 10 in hand, we are now in position to prove Theorem 2.

Proof of Theorem 2.

The duals of the Venn diagrams from Theorem 1 all have a colorful face, namely the outer face $C(x_{1})$ , so applying Lemma 10 ( $m$ times) proves the theorem. $\hfill\blacktriangleleft$

6 Remarks and open problems

We conclude with some remarks and challenging open problems.

$\blacksquare$

Is there a minimum 8-Venn diagram, i.e., one with only 37 crossings? The best one we found has 40 crossings; see Figure 3.
$\blacksquare$

Lemma 7 gives a Hamiltonian path $P$ in $Q_{n}$ , $n=2^{k}$ , with

$\nu_{n-1}(P)+2\lambda_{n-1}(P)=2\cdot 2^{n}-\frac{33}{8}\cdot\frac{2^{n}}{n}+4.$

Is there another construction that would decrease the constant $\frac{33}{8}$ ? If so, then this would directly improve the same constant in Theorems 1 and 2. One can easily prove an upper bound of $\nu_{n-1}(P)+2\lambda_{n-1}(P)\leq 2\cdot 2^{n}-\frac{2^{n}}{n}$ .
$\blacksquare$

A long-standing problem due to Slater [21] is whether there exists a Hamiltonian path $P$ in $Q_{n}$ such that any two consecutive entries of the flip sequence differ by $\pm 1$ . Put differently, if we write $\mu(P)$ for the number of such consecutive entries of $\sigma(P)$ , then the goal is to find a Hamiltonian path $P$ with $\mu(P)=2^{n}-2$ . While such a path exists for $n\leq 6$ , it does not exist for $n=7$ [22] and $n=8$ (computer experiments by Dimitrov, Gregor and Lužar; see [17, Problem 10]). We clearly have $\mu(P)\geq\lambda_{n}(P)\geq\lambda_{n-1}(P)$ , so Lemma 7 and Corollary 8 yield a Hamiltonian path $P$ for which $\mu(P)=(1-o(1))\cdot(2^{n}-2)$ , which can be seen as an approximate solution to Slater’s problem (cf. [14]).

References

[1] Sofia Brenner, Petr Gregor, Torsten Mütze, and Francesco Verciani. On minimum Venn diagrams, 2025. arXiv:2511.09230.
[2] Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani. Disproving two conjectures on the Hamiltonicity of Venn diagrams, 2025. arXiv:2503.18554.
[3] Bette Bultena, Branko Grünbaum, and Frank Ruskey. Convex drawings of intersecting families of simple closed curves. In Canadian Conference on Computational Geometry (CCCG), 1999. URL: http://www.cccg.ca/proceedings/1999/c14.pdf.
[4] Bette Bultena and Frank Ruskey. Venn diagrams with few vertices. Electron. J. Combin., 5:Research Paper 44, 21 pp., 1998. doi:10.37236/1382.
[5] Kiran B. Chilakamarri, Peter Hamburger, and Raymond E. Pippert. Venn diagrams and planar graphs. Geom. Dedicata, 62(1):73–91, 1996. doi:10.1007/BF00240003.
[6] Kiran B. Chilakamarri, Peter Hamburger, and Raymond E. Pippert. Analysis of Venn diagrams using cycles in graphs. Geom. Dedicata, 82(1-3):193–223, 2000. doi:10.1023/A:1005288325189.
[7] Anthony W. F. Edwards. Venn diagrams for many sets. In Bulletin of the International Statistical Institute, 47th Session, Paris, Book 1, pages 311–312. IIS, 1989.
[8] Anthony W. F. Edwards. Venn diagrams for many sets. New Scientist, 121(1646):51–56, 1989.
[9] Paul Erdős and Richard K. Guy. Crossing number problems. Amer. Math. Monthly, 80:52–58, 1973. doi:10.2307/2319261.
[10] Jerrold R. Griggs, Charles E. Killian, and Carla D. Savage. Venn diagrams and symmetric chain decompositions in the boolean lattice. Electron. J. Comb., 11(1), 2004. doi:10.37236/1755.
[11] Branko Grünbaum. Venn diagrams. I. Geombinatorics, 1(4):5–12, 1992.
[12] Peter Hamburger and Raymond E. Pippert. Simple, reducible Venn diagrams on five curves and Hamiltonian cycles. Geom. Dedicata, 68(3):245–262, 1997. doi:10.1023/A:1004924423245.
[13] David W. Henderson. Classroom Notes: Venn Diagrams for More than Four Classes. Amer. Math. Monthly, 70(4):424–426, 1963. doi:10.2307/2311865.
[14] Gabriel S. Himelfarb and Moshe Schwartz. Improved constructions of skew-tolerant gray codes. IEEE Trans. Inform. Theory, 71(10):8017–8028, 2025. doi:10.1109/tit.2025.3592490.
[15] Charles E. Killian, Frank Ruskey, Carla D. Savage, and Mark Weston. Half-simple symmetric Venn diagrams. Electron. J. Comb., 11(1), 2004. doi:10.37236/1839.
[16] Khalegh Mamakani and Frank Ruskey. New roses: Simple symmetric Venn diagrams with 11 and 13 curves. Discret. Comput. Geom., 52(1):71–87, 2014. doi:10.1007/S00454-014-9605-6.
[17] Torsten Mütze. Combinatorial Gray codes—an updated survey. Electron. J. Combin., DS26(Dynamic Surveys):93 pp., 2023. doi:10.37236/11023.
[18] Mark Ramras. Symmetric vertex partitions of hypercubes by isometric trees. J. Combin. Theory Ser. B, 54(2):239–248, 1992. doi:10.1016/0095-8956(92)90055-3.
[19] Frank Ruskey and Mark Weston. A survey of Venn diagrams. Electron. J. Combin., 4(1):Dynamic Survey 5, 1997. doi:10.37236/26.
[20] Marcus Schaefer. The graph crossing number and its variants: a survey. Electron. J. Combin., DS21(Dynamic Surveys):90 pp., 2013. doi:10.37236/2713.
[21] Peter J. Slater. A problem concerning restricted Gray codes, open problem session. Congr. Numer., XXIII–XIV:918–919, 1979. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1979).
[22] Peter J. Slater. Research problems 109 and 110. Discrete Math., 76(3):293–294, 1989. doi:10.1016/0012-365X(89)90330-0.
[23] William T. Tutte. A theorem on planar graphs. Trans. Amer. Math. Soc., 82:99–116, 1956. doi:10.2307/1992980.
[24] John Venn. On the diagrammatic and mechanical representation of propositions and reasonings. Phil. Mag. S. 5., 9(59):1–18, 1880. doi:10.1080/14786448008626877.
[25] Hassler Whitney. A theorem on graphs. Ann. of Math. (2), 32(2):378–390, 1931. doi:10.2307/1968197.
[26] Peter Winkler. Venn diagrams: Some observations and an open problem. Congr. Numer., 45:267–274, 1984.
[27] Peter Winkler. Mathematical puzzles: A connoisseur’s collection. AK Peters Series, Taylor & Francis, 2004.
[28] Peter Winkler. Puzzled: Where sets meet (Venn diagrams). Commun. ACM, 55(2):128, 2012. doi:10.1145/2076450.2076475.

[bib.bib1] [1] Sofia Brenner, Petr Gregor, Torsten Mütze, and Francesco Verciani. On minimum Venn diagrams, 2025. arXiv:2511.09230.

[bib.bib2] [2] Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani. Disproving two conjectures on the Hamiltonicity of Venn diagrams, 2025. arXiv:2503.18554.

[bib.bib3] [3] Bette Bultena, Branko Grünbaum, and Frank Ruskey. Convex drawings of intersecting families of simple closed curves. In Canadian Conference on Computational Geometry (CCCG), 1999. URL: http://www.cccg.ca/proceedings/1999/c14.pdf.

[bib.bib4] [4] Bette Bultena and Frank Ruskey. Venn diagrams with few vertices. Electron. J. Combin., 5:Research Paper 44, 21 pp., 1998. doi:10.37236/1382.

[bib.bib5] [5] Kiran B. Chilakamarri, Peter Hamburger, and Raymond E. Pippert. Venn diagrams and planar graphs. Geom. Dedicata, 62(1):73–91, 1996. doi:10.1007/BF00240003.

[bib.bib6] [6] Kiran B. Chilakamarri, Peter Hamburger, and Raymond E. Pippert. Analysis of Venn diagrams using cycles in graphs. Geom. Dedicata, 82(1-3):193–223, 2000. doi:10.1023/A:1005288325189.

[bib.bib7] [7] Anthony W. F. Edwards. Venn diagrams for many sets. In Bulletin of the International Statistical Institute, 47th Session, Paris, Book 1, pages 311–312. IIS, 1989.

[bib.bib8] [8] Anthony W. F. Edwards. Venn diagrams for many sets. New Scientist, 121(1646):51–56, 1989.

[bib.bib9] [9] Paul Erdős and Richard K. Guy. Crossing number problems. Amer. Math. Monthly, 80:52–58, 1973. doi:10.2307/2319261.

[bib.bib10] [10] Jerrold R. Griggs, Charles E. Killian, and Carla D. Savage. Venn diagrams and symmetric chain decompositions in the boolean lattice. Electron. J. Comb., 11(1), 2004. doi:10.37236/1755.

[bib.bib11] [11] Branko Grünbaum. Venn diagrams. I. Geombinatorics, 1(4):5–12, 1992.

[bib.bib12] [12] Peter Hamburger and Raymond E. Pippert. Simple, reducible Venn diagrams on five curves and Hamiltonian cycles. Geom. Dedicata, 68(3):245–262, 1997. doi:10.1023/A:1004924423245.

[bib.bib13] [13] David W. Henderson. Classroom Notes: Venn Diagrams for More than Four Classes. Amer. Math. Monthly, 70(4):424–426, 1963. doi:10.2307/2311865.

[bib.bib14] [14] Gabriel S. Himelfarb and Moshe Schwartz. Improved constructions of skew-tolerant gray codes. IEEE Trans. Inform. Theory, 71(10):8017–8028, 2025. doi:10.1109/tit.2025.3592490.

[bib.bib15] [15] Charles E. Killian, Frank Ruskey, Carla D. Savage, and Mark Weston. Half-simple symmetric Venn diagrams. Electron. J. Comb., 11(1), 2004. doi:10.37236/1839.

[bib.bib16] [16] Khalegh Mamakani and Frank Ruskey. New roses: Simple symmetric Venn diagrams with 11 and 13 curves. Discret. Comput. Geom., 52(1):71–87, 2014. doi:10.1007/S00454-014-9605-6.

[bib.bib17] [17] Torsten Mütze. Combinatorial Gray codes—an updated survey. Electron. J. Combin., DS26(Dynamic Surveys):93 pp., 2023. doi:10.37236/11023.

[bib.bib18] [18] Mark Ramras. Symmetric vertex partitions of hypercubes by isometric trees. J. Combin. Theory Ser. B, 54(2):239–248, 1992. doi:10.1016/0095-8956(92)90055-3.

[bib.bib19] [19] Frank Ruskey and Mark Weston. A survey of Venn diagrams. Electron. J. Combin., 4(1):Dynamic Survey 5, 1997. doi:10.37236/26.

[bib.bib20] [20] Marcus Schaefer. The graph crossing number and its variants: a survey. Electron. J. Combin., DS21(Dynamic Surveys):90 pp., 2013. doi:10.37236/2713.

[bib.bib21] [21] Peter J. Slater. A problem concerning restricted Gray codes, open problem session. Congr. Numer., XXIII–XIV:918–919, 1979. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1979).

[bib.bib22] [22] Peter J. Slater. Research problems 109 and 110. Discrete Math., 76(3):293–294, 1989. doi:10.1016/0012-365X(89)90330-0.

[bib.bib23] [23] William T. Tutte. A theorem on planar graphs. Trans. Amer. Math. Soc., 82:99–116, 1956. doi:10.2307/1992980.

[bib.bib24] [24] John Venn. On the diagrammatic and mechanical representation of propositions and reasonings. Phil. Mag. S. 5., 9(59):1–18, 1880. doi:10.1080/14786448008626877.

[bib.bib25] [25] Hassler Whitney. A theorem on graphs. Ann. of Math. (2), 32(2):378–390, 1931. doi:10.2307/1968197.

[bib.bib26] [26] Peter Winkler. Venn diagrams: Some observations and an open problem. Congr. Numer., 45:267–274, 1984.

[bib.bib27] [27] Peter Winkler. Mathematical puzzles: A connoisseur’s collection. AK Peters Series, Taylor & Francis, 2004.

[bib.bib28] [28] Peter Winkler. Puzzled: Where sets meet (Venn diagrams). Commun. ACM, 55(2):128, 2012. doi:10.1145/2076450.2076475.

On Minimum Venn Diagrams

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Maximizing and minimizing the number of crossings

1.2 Our results

Theorem 1.

Theorem 2.

1.3 Duals of Venn diagrams

1.4 Proof ideas

2 Isometric partitions of hypercubes

2.1 Preliminaries

2.2 Partition into isometric paths

Theorem 3 ([18, Thm. 2.5]).

2.3 Finding another basis for ⟨𝑩𝒌⟩

Lemma 4.

2.4 Partition into isometric cycles

Corollary 5.

Lemma 6.

3 Long-run Gray code construction

Lemma 7.

Proof.

Corollary 8.

Proof.

4 Proof of Theorem 1

Lemma 9.

Proof.

Proof of Theorem 1.

5 Proof of Theorem 2

Lemma 10.

Proof of Theorem 2.

6 Remarks and open problems

References

2.3 Finding another basis for $\langle B_{k}\rangle$