# Irreducible Subcube Partitions

Yuval Filmus, Edward A. Hirsch, Sascha Kurz, Ferdinand Ihringer,
Artur Riazanov, Alexander Smal, Marc Vinyals

###### Abstract

A _subcube partition_ is a partition of the Boolean cube $\\{0,1\\}^{n}$ into
subcubes. A subcube partition is _irreducible_ if the only sub-partitions
whose union is a subcube are singletons and the entire partition. A subcube
partition is _tight_ if it ‘‘mentions’’ all coordinates.

We study extremal properties of tight irreducible subcube partitions: minimal
size, minimal weight, maximal number of points, maximal size, and maximal
minimum dimension. We also consider the existence of _homogeneous_ tight
irreducible subcube partitions, in which all subcubes have the same
dimensions. We additionally study subcube partitions of
$\\{0,\dots,q-1\\}^{n}$, and partitions of $\mathbb{F}_{2}^{n}$ into affine
subspaces, in both cases focusing on the minimal size.

Our constructions and computer experiments lead to several conjectures on the
extremal values of the aforementioned properties.

##  1 Introduction

A _subcube partition_ is a partition of the cube $\\{0,1\\}^{n}$ into
subcubes, that is, into sets of the form

$\\{x\in\\{0,1\\}^{n}:x_{i_{1}}=b_{1},\ldots,x_{i_{d}}=b_{d}\\}.$

Here is an example of a subcube partition of _length_ $n=3$:

$\displaystyle S_{3}$
$\displaystyle=\\{000\\},\\{111\\},\\{001,101\\},\\{100,110\\},\\{010,011\\}$
$\displaystyle=000,111,*01,1*0,01*.$

We will usually express our subcubes as strings in $\\{0,1,*\\}^{n}$, in which
stars stand for unconstrained coordinates.

A subcube partition is _reducible_ if it has a proper subset, consisting of
more than one subcube, whose union is a subcube. For example,

$0*,10,11$

is reducible since $10\cup 11=1*$. In contrast, $S_{3}$ is _irreducible_.

A subcube partition is _tight_ if it _mentions_ all coordinates, that is, if
for every $i\in[n]$, some subcube constrains $x_{i}$. Both subcube partitions
above are tight, but the subcube partition $0*,1*$ is not, since the second
coordinate is not mentioned.

Peitl and Szeider [PS23] enumerated all tight irreducible subcube partitions
for $n=3,4$, and counted the number of nonisomorphic subcube partitions with
small _size_ (number of subcubes) for $n=5,6,7$. They ask whether there are
infinitely many tight irreducible subcube partitions. In this work, we answer
this question in the affirmative, giving many constructions of tight
irreducible subcube partitions.

The work of Peitl and Szeider raises many natural questions, such as:

  * •

How to determine whether a subcube partition is irreducible?

  * •

What is the minimal size of a tight irreducible subcube partition of length
$n$?
(This question only makes sense if we impose tightness.)

  * •

What is the maximal size of an irreducible subcube partition of length $n$?

  * •

Do there exist irreducible subcube partitions in which all subcubes have the
same dimension?
(We call such subcube partitions _homogeneous_.)

We address these questions in Section 2. We describe an efficient algorithm
for testing whether a subcube partition is irreducible in Section 2.1, and
give two infinite sequences of irreducible formulas in Section 2.2.

We conjecture that the minimal size of a tight irreducible subcube partition
of length $n$ is $2n-1$. We give a matching construction in Section 2.3, and
optimize its Hamming weight in Section 2.4 (this will be useful later on).

We conjecture that the maximal size of an irreducible subcube partition of
length $n\geq 5$ is $\tfrac{5}{8}2^{n}$. We give a matching construction in
Section 2.6, where we also give a nontrivial upper bound. Our constructions
involve $2^{n-2}$ points ($0$-dimensional subcubes) and $3\cdot 2^{n-3}$ edges
($1$-dimensional subcubes). We conjecture that $2^{n-2}$ is the maximum number
of points in an irreducible subcube partition of size $n$. A simple matching
construction appears in Section 2.5.

We present subcube partitions in which all subcubes have linear dimension in
Section 2.7. We close off the section with a discussion of homogeneous subcube
partitions in Section 2.8, where we describe several constructions, and
determine all lengths $n$ and codimensions $k\leq 4$ for which there exists a
tight irreducible subcube partition of length $n$ whose subcubes have
dimension $n-k$. In particular, we describe a construction due to Perezhogin
[Per05] of irreducible subcube partitions of all length $n\geq 7$ in which all
subcubes have dimension $1$.

Section 3 studies subcube partitions of $[q]^{n}$ for $q\geq 3$. We show how
to construct irreducible subcube partitions of $[q]^{n}$ from irreducible
subcube partitions of $\\{0,1\\}^{n}$ in Section 3.1, and use this to
construct tight irreducible subcube partitions of length $n$ and size
$(n-1)q(q-1)+1$ in Section 3.2.1; this uses the subcube partitions of Section
2.4. We conjecture that $(n-1)q(q-1)+1$ is the minimum size of a tight
irreducible subcube partition, and prove this for $n=3$ in Section 3.2.2. We
close by showing, in Section 3.2.3, that the minimal size of a tight _minimal
cover_ in this setting is $(q-1)n+1$.

Finally, Section 4 briefly studies the linear analog of subcube partitions, in
which subcubes are replaced by affine subspaces. We show how to construct
irreducible affine vector space partitions from irreducible subcube partitions
in Section 4.1, and use this to construct tight irreducible affine subspace
partitions of length $n$ and size roughly $\tfrac{3}{2}n$ in Section 4.2. We
discuss irreducible affine vector space partitions in more detail in the
companion work [BFIK23].

### Background

Subcube partitions appear, under various names, in theoretical computer
science, as an abstraction of the salient properties of decision trees, and
elsewhere. Some examples include Iwama [Iwa87, Iwa89] (as certain _independent
sets of clauses_), Brandman, Orlitsky and Hennessy [BOH90] (as _nonoverlapping
covers_), Berger, Felzanbaum and Fraenkel [BFF90] (as _disjoint tautologies_),
Davydov and Davydova [DD98] (as _dividing formulas_), Friedgut, Kahn and
Wigderson [FKW02] (as _subcube partitions_), Kullmann [Kul04] (as
_unsatisfiable hitting clause-sets_), Kisielewicz [Kis20] (as realizations of
_cube tiling codes_), Tarannikov [Tar22] (as _coordinate partitions_). There
are also _orthogonal DNFs_ [CH11], also known as _disjoint DNFs_ [GK13], which
are systems of disjoint subcubes which do not necessarily cover the entire
cube. (For the relation between decision trees and subcube partitions, see
Göös, Pitassi and Watson [GPW18].)

Irreducible subcube partitions appear in a work of Kullmann and Zhao [KZ16]
(as _clause-reducibility_), inspired by similar notions in the context of
disjoint covering systems of residue classes [Kor84, BFF90] and motivated by
applications to the study of CNFs.

Peitl and Szeider [PS23] enumerate all tight irreducible subcube partitions
for $n=3,4$, and determine the minimal size of a regular irreducible subcube
partition for $n=5,6,7$. Instead of tightness, they use a different notion,
_regularity_ , which is equivalent to tightness for irreducible subcube
partitions when $n\geq 3$. Regularity was introduced by Kullmann and Zhao
[KZ13] under the name _nonsingularity_ , and is defined in Section 2.3.1.

##### Acknowledgements

We thank Jan Johannsen, Ilario Bonacina, Oliver Kullmann, and Stefan Szeider
for introducing us to the topic; Tomáš Peitl and Stefan Szeider for sharing
with us the results of the computer search reported in [PS23]; Zachary Chase
for helpful discussions; Yuriy Tarannikov for bringing into our attention the
papers [Per05, Agi08, Tar22] and helping us to understand [Per05]; Andrzej
Kisielewicz for simplifying several of our proofs and for bringing into our
attention [Kis14, KP08]; and the anonymous reviewer for their careful reading
of the manuscript and helpful comments.

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 802020-ERC-
HARMONIC. Ferdinand Ihringer is supported by a postdoctoral fellowship of the
Research Foundation – Flanders (FWO).

##  2 Subcube partitions

We start with a quick recap of the relevant definitions.

######  Definition 2.1 (Subcube partition).

A _subcube partition_ of length $n$ is a partition of $\\{0,1\\}^{n}$ into
_subcubes_ , which are sets of the form

$\\{x\in\\{0,1\\}^{n}:x_{i_{1}}=b_{1},\ldots,x_{i_{d}}=b_{d}\\}.$

The parameter $d$ is the _codimension_ of the subcube, and $n-d$ is its
_dimension_. A subcube of dimension $0$ is called a _point_ , and a subcube of
dimension $1$ is called an _edge_.

The _size_ of a subcube partition is the number of subcubes.

We identify subcubes with words over $\\{0,1,*\\}$. For example, $01*$ stands
for the subcube $\\{(0,1,0),(0,1,1)\\}$. We index the symbols in a word $w$ of
length $n$ by $[n]=\\{1,\dots,n\\}$. If $b\in\\{0,1\\}$, we use $\bar{b}$ to
denote $1-b$.

######  Definition 2.2 (Reducibility).

A subcube partition $F$ is _reducible_ if there exists a subset $G\subset F$,
with $1<|G|<|F|$, such that the union of the subcubes in $G$ is itself a
subcube.

A subcube partition is _irreducible_ if it is not reducible.

######  Definition 2.3 (Tightness).

A subcube $s$ _mentions_ a coordinate $i\in[n]$ if $s_{i}\neq*$.

A subcube partition $F$ of length $n$ is _tight_ if for every $i\in[n]$, some
subcube in $F$ mentions $i$.

It is coNP-complete to determine whether a given collection of subcubes covers
$\\{0,1\\}^{n}$ (this problem is just SAT in disguise). In contrast, it is
easy to test whether a given collection of subcubes is a partition, as first
observed by Iwama [Iwa89].

######  Definition 2.4 (Conflicting subcubes).

Two subcubes $s,t$ of the same length are said to _conflict_ if there is a
coordinate $i\in[n]$ such that $s_{i},t_{i}\neq*$ and $s_{i}\neq t_{i}$.

######  Lemma 2.5.

Two subcubes are disjoint if and only if they conflict.

######  Lemma 2.6.

A collection $F$ of disjoint subcubes of length $n$ is a subcube partition if
and only if

$\sum_{s\in F}2^{-\operatorname{codim}(s)}=1.$

Similarly, it is easy to check whether a given subcube partition is tight. In
contrast, checking whether a subcube partition is irreducible using the
definition takes exponential time. We present an efficient algorithm for
testing irreducibility in Section 2.1.

Following that, we give many examples of irreducible subcube partitions,
starting with Section 2.2, which describes subcube partitions whose
irreducibility can be proved using a simple parity argument. In Sections 2.3,
2.4, 2.5, 2.6 and 2.7 we describe irreducible subcube partitions which
conjecturally optimize various parameters. Section 2.8 closes with a
discussion of irreducible subcube partitions in which all subcubes have the
same dimension.

###  2.1 Testing irreducibility

In this section we give a polynomial time algorithm that checks whether a
given subcube partition $F$ is reducible, and if so, identifies a subset
$G\subset F$, with $1<|G|<|F|$, whose union is a subcube.

The idea behind the algorithm is quite simple. Suppose that $F$ were
reducible, say via the subset $G$. If $s,t\in G$ then $\bigcup G$ must contain
the _join_ $s\lor t$ of $s,t$, which is the smallest subcube containing both
$s$ and $t$, given explicitly by

$(s\lor t)_{i}=\begin{cases}b&\text{if }s_{i}=t_{i}=b\in\\{0,1\\},\\\
*&\text{otherwise}.\end{cases}$

If $u\in F$ intersects $s\lor t$ (a condition we can check using Lemma 2.5)
then $G$ must contain $u$, and so $\bigcup G$ must contain $s\lor t\lor u$.
Continuing in this way, we are able to recover $G$ (or a subset of $G$ whose
union is also a subcube). The corresponding algorithm appears as Algorithm 1.

0: Subcube partition $F=\\{s_{1},\dots,s_{m}\\}$

for $1\leq i<j\leq m$ do

$G\leftarrow\\{s_{i},s_{j}\\}$

while some $s_{k}\notin G$ intersects $\bigvee G$ do

$G\leftarrow G\cup\\{s_{k}\\}$

end while

if $G\neq F$ then

return Reducible: $\bigcup G$ is a subcube

end if

end for

return Irreducible

Algorithm 1 Algorithm for checking whether a subcube partition is irreducible

######  Theorem 2.7.

Algorithm 1 runs in polynomial time, and its output is correct.

###### Proof.

We start by showing that the algorithm runs in polynomial time. The outer for
loop runs $O(m^{2})$ times, and the inner while loop runs at most $m$ times.
Each basic operation can be implemented in polynomial time, and so the entire
algorithm runs in polynomial time.

Suppose first that the algorithm outputs ‘‘reducible’’. By construction, all
subcubes in $F\setminus G$ are disjoint from $\bigvee G$. Since $F$ is a
subcube partition, this means that $\bigcup G=\bigvee G$, which is a subcube.
By construction, $1<|G|<|F|$, and so $F$ is indeed reducible.

To complete the proof, we show that if $F$ is reducible, then the algorithm
outputs ‘‘reducible’’. If $F$ is reducible then there is a subset $H\subset
F$, with $1<|H|<|F|$, such that $\bigcup H$ is a subcube. Let $s_{i},s_{j}\in
H$, and consider the $(i,j)$ iteration of the outer for loop.

We prove inductively that at each iteration of the inner while loop, $G$ is
contained in $H$. This holds by construction at the very first step. Now
suppose that $G\subseteq H$ and that $s_{k}\notin G$ intersects $\bigvee G$.
Since $G\subseteq H$, also $\bigvee G\subseteq\bigvee H$, and so $s_{k}$
intersects $\bigvee H$. Since $\bigvee H=\bigcup H$ and the subcubes in $F$
are disjoint, necessarily $s_{k}\in H$. Hence $G\cup\\{s_{k}\\}\subseteq H$.

When the while loop ends, all $s_{k}\notin G$ are disjoint from $\bigvee G$.
Since the subcubes in $F$ are disjoint, this means that $\bigvee G=\bigcup G$.
Since $G\subseteq H$, necessarily $G\neq F$, and so the algorithm correctly
declares that $F$ is reducible. ∎

###  2.2 Parity argument

In this section we present two constructions of infinite families of tight
irreducible subcube partitions.

######  Theorem 2.8.

Let $n=2m+1\geq 3$. The following subcubes comprise a tight irreducible
subcube partition of size $\Theta(n^{3})$:

  * •

The point $0^{n}$.

  * •

All cyclic rotations of $0^{m}1*^{m}$.

  * •

For every $0\leq i,j,k\leq m-1$ satisfying $i+j,j+k\leq m-1$, the subcube

$0^{i}1*^{j}0^{k}1*^{m-1-j-k}0^{j}1*^{m-1-i-j}.$

We found this subcube partition by starting with the subcube partition
consisting of all rotations of $0^{m}1*^{m}$ together with all points not
covered by them. This subcube partition is reducible, and we can use Algorithm
1 to merge together points into subcubes. One can show inductively that the
rotations of $0^{m}1*^{m}$ never get merged, and so the resulting subcube
partition is not trivial. It is precisely the one described in Theorem 2.8.

Here is the resulting partition for $n=5$:

$\begin{array}[]{cccccc}00000&001**&*001*&**001&1**00&01**0\\\
&11*1*&1011*&011*1&01011&1*101\end{array}$

######  Theorem 2.9.

Let $n\geq 1$ be odd. The following subcubes comprise a tight irreducible
subcube partition of size $F_{n+1}+F_{n-1}+1$, where $F_{n}$ is the $n$’th
Fibonacci number:

  * •

The point $1^{n}$.

  * •

All subcubes obtained by concatenating blocks of the form $*1$ or $0$ in an
arbitrary way, and rotating the result arbitrarily.

This subcube partition appears in [Kis14, Section 2], where it is attributed
to Lagarias and Shor [LS94]. Here is the partition for $n=5$:

$\begin{array}[]{cccccc}00000&*1000&0*100&00*10&000*1&1000*\\\
11111&*1*10&*10*1&0*1*1&1*10*&10*1*\end{array}$

In both cases, we will prove the irreducibility using the following lemma,
suggested to us by Kisielewicz.

######  Definition 2.10 (Star pattern).

The _star pattern_ of a subcube $s\in\\{0,1,*\\}^{n}$ is
$P(s):=\\{i\in[n]:s_{i}=*\\}$.

######  Definition 2.11 (Parity of a subcube).

The _parity_ of a subcube $s\in\\{0,1,*\\}^{n}$ is the parity of the number of
$1$s in $s$.

######  Lemma 2.12 ([Kis23]).

Let $F$ be a subcube partition. Let $G$ be a subset of $F$ such that $|G|>1$
and the union of $G$ is a subcube. Let $S$ be an inclusion-minimal star
pattern occurring in $G$ (this means that no star pattern strictly contained
in $S$ appears in $G$).

Among subcubes in $G$ whose star pattern is $S$, half have even parity and
half have odd parity.

###### Proof.

Let $C\subseteq\bigcup G$ consist of all points $p$ such that $p_{i}=0$ for
all $i\in S$. If $|C|=1$ then $S$ is the star pattern of $\bigcup G$, which
contradicts $|G|>1$. Hence $|C|>1$. Since $C$ is a subcube, it contains an
equal number of points of even parity and of odd parity.

If $s\in G$ has star pattern other than $S$ then by inclusion-minimality,
$s_{i}=*$ for some $i\notin S$. Therefore $s\cap C$ contains an equal number
of points of even parity and of odd parity. In contrast, if $s\in G$ has star
pattern $S$ then $s\cap C$ contains a single point whose parity is the same as
the parity of $s$. Since $C$ has an equal number of points of either parity,
the lemma immediately follows. ∎

######  Corollary 2.13.

Let $F$ be a subcube partition in which there is a star pattern $S$ occurring
twice, and every other star pattern occurs at most once. If $G$ is a subset of
$F$ whose union is a subcube and $|G|>1$ then $G$ contains both subcubes of
$F$ whose star pattern is $S$.

###### Proof.

Let $U$ be an inclusion-minimal star pattern in $G$. Lemma 2.12 implies that
$G$ must contain an even number of subcubes whose star pattern is $U$.
Necessarily $U=S$, and so $G$ contains both subcubes whose star pattern in
$S$. ∎

Corollary 2.13 almost immediately implies the irreducibility of the subcube
partition in Theorem 2.9: any non-singleton subset of the subcube partition
whose union is a subcube must contain both points $0^{n},1^{n}$, and so its
union must be $\\{0,1\\}^{n}$. The argument for Theorem 2.8 is only slightly
longer.

We prove Theorem 2.8 in Section 2.2.1, and Theorem 2.9 in Section 2.2.2.

####  2.2.1 Cubic construction

In this section we prove Theorem 2.8.

We need to prove three things about the set of subcubes $F$ given in the
statement of the theorem: that it is a subcube partition; that it is tight;
and that it is irreducible.

##### Subcube partition

The point $0^{n}$ covers itself. All other subcubes of $F$ contain at least
one $1$.

Subcubes of the second type cover _royal points_. These are points which
contain a _royal $1$_, which is a $1$ preceded cyclically by $m$ many $0$s.
Since $n<2(m+1)$, there can be at most one royal $1$, and so royal points are
covered by precisely one subcube of the second type. We will soon see that
they are not covered by any subcube of the third type.

We can guarantee that a subcube does not contain any royal point by adding
‘‘blocking $1$s’’: if each cyclic interval of length $m$ contains a $1$, then
the subcube cannot contain any royal point. Each subcube of the third type is
contained in the subcube $*^{i}1*^{j+k}1*^{m-1-k}1*^{m-1-i-j}$, in which the
$1$s are separated by $j+k,m-1-k,m-1-j\leq m-1$ many stars. Consequently, each
royal point is covered by precisely one subcube of $F$.

It remains to handle points $x\neq 0^{n}$ which are not royal. Let $I+1$ be
the index of the first $1$ in $x$. Since $x$ is not royal, $I\leq m-1$.

Let $I+1+m+J+1$ be the first $1$ in $x$ beyond position $I+1+m$ (so $J\geq
0$). Such a $1$ exists since otherwise $x$ starts with $0^{I}1$ and ends with
$0^{m-I}$, and is consequently royal. For the same reason, $J\leq m-1$. Since
$I+1+m+J+1\leq n$, we see that $I+J\leq m-1$.

Let $I+1+J+K+1$ be the first $1$ in $x$ beyond position $I+1+J$ (so $K\geq
0$). Such a $1$ exists as seen before. Since $x$ is not royal, $J+K\leq m-1$.
Collecting all the information, we see that $x$ belongs to the subcube of the
third type

$\displaystyle 0^{I}1*^{J}\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0^{K}1*^{m-1-J-K}\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>$I+1+J$$I+1+m$

If $x\in 0^{i}1*^{j}0^{k}1*^{m-1-j-k}0^{j}1*^{m-1-i-j}$ and we follow the
steps above then we find that $i=I$, $j=J$, and $k=K$. Therefore $x$ belongs
to a unique subcube of $F$.

##### Tightness

This is clear, since the subcube $0^{n}$ mentions all coordinates.

##### Irreducibility

We will use Corollary 2.13 in order to prove irreducibility, so we first need
to understand the star patterns of the various subcubes in $F$.

A subcube of the second type has precisely $m$ stars, and each subcube of the
second type has a different star pattern. Furthermore, each star pattern
either consists of a single interval, or of one interval starting at $1$ and
another interval ending at $n$.

A subcube of the third type has no interval of $m$ stars, and cannot start
with a star, hence its star patterns differ from those of subcubes of the
second type. Given the star pattern of a subcube of the third type, we can
determine $i,j,k$. First, we determine $i+j$ by counting the number of
trailing stars, which is $m-1-i-j$. This allows us to determine $j$ (and so
$i$), by counting the number of stars in the first $i+1+j$ symbols. We can now
determine $k$ by counting the number of stars in the first $i+1+m$ symbols,
which is $m-1-k$.

Summarizing, if we consider only subcubes of the second and third types, then
all star patterns are unique. Considering the entire subcube partition, there
is one star pattern occurring twice, corresponding to the points $0^{n}$ and
$0^{m-1}10^{m-1}11$, and all other star patterns occur once.

If $F$ were reducible then there would be a subset $G\subseteq F$ such that
$1<|G|<|F|$ and the union of $G$ is a subcube. According to Corollary 2.13,
$G$ must contain both points $0^{n},0^{m-1}10^{m-1}11$, and so $\bigcup G$
must contain their join $0^{m-1}*0^{m-1}**$. This implies that $G$ must cover
the point $0^{m-1}10^{m-1}00$, and so must contain the subcube
$0^{m-1}1*^{m}0$. Similarly, it must cover the point $0^{m-1}00^{m-1}10$, and
so contain the subcube $*^{m-1}0^{m}1*$. Since the join of the latter two
subcubes is $*^{n}$, we conclude that $G=F$, contrary to assumption. Therefore
$F$ is irreducible.

####  2.2.2 Lagarias–Shor construction

In this section we prove Theorem 2.9.

We need to prove three things about the set of subcubes $F$ given in the
statement of the theorem: that it is a subcube partition; that it is tight;
and that it is irreducible. (We leave it to the reader to prove the formula
for the size of $F$.)

##### Subcube partition

The point $1^{n}$ covers itself. Since $n$ is odd, every other subcube
contains $0$, and so doesn’t cover $1^{n}$.

Consider now a point $x\in\\{0,1\\}^{n}$ other than $1^{n}$. We will convert
it, in stages, to a subcube $y\in F$ which contains it.

We initialize $y$ with $x$. If there is an index $i$ such that $y_{i}=1$ and
$y_{i+1}\neq 1$ (treating indices cyclically) then any subcube in $F$ which
covers $y$ must have $y_{i}=1$ and so $y_{i-1}=*$. Accordingly, as long as
there is an index $i$ such that $y_{i-1}\neq*$, $y_{i}=1$, $y_{i+1}\neq 1$, we
set $y_{i-1}=*$.

When the process stops, every $1$ is either preceded by $*$ or followed by
$1$. Since $x\neq 1^{n}$, every run of $1$ in $y$ must terminate (followed by
$*$ or $0$). The final $1$ in each such run is not followed by $1$, and so
must be preceded by $*$ (implying that the run has length $1$). It follows
that $y$ is, up to rotation, a concatenation of copies of $*1$ and $0$, and so
$y\in F$. Furthermore, the construction of $y$ ensures that this is the only
subcube in $F$ covering $x$.

##### Tightness

This is clear, since the subcube $1^{n}$ mentions all coordinates.

##### Irreducibility

In view of using Corollary 2.13, we first explore the star patterns of the
various subcubes in $F$. The main observation is that we can recover a subcube
of the second type from its star pattern. Indeed, every star must be followed
by $1$, and every position not preceded by a star must be $0$. This implies
that apart from the two points $0^{n},1^{n}$, all other star patterns are
unique.

If $F$ were reducible then there would exist a subset $G\subset F$ with
$1<|G|<|F|$ whose union is a subcube. Corollary 2.13 shows that $G$ must
contain both points $0^{n},1^{n}$, and so their join $*^{n}$, contradicting
the assumption $G\neq F$. Hence $F$ is irreducible.

###  2.3 Minimal size

What is the minimal size of a tight irreducible subcube partition of length
$n$? (The question doesn’t make sense without assuming tightness, since
$*^{n}$ is always irreducible.)

When $n=1$, there is a single tight irreducible subcube partition: $0,1$. When
$n=2$, there are no tight irreducible subcube partitions. When $n=3$, there is
a unique tight irreducible subcube partition, up to flipping and rearranging
coordinates:

$000,*01,1*0,01*,11.$

For $n=4,5,6,7$, Peitl and Szeider [PS23] used a computer search to show that
the minimal number of subcubes is $7,9,11,13$, respectively. This is
consistent with the following conjecture.

######  Conjecture 1.

If $n\geq 3$ then the minimal size of a tight irreducible subcube partition of
length $n$ is $2n-1$.

Section 2.3.1 explains the best lower bound on the size, due to Kullmann and
Zhao [KZ13]. Sections 2.3.2 and 2.3.3 present two constructions of an infinite
family of tight irreducible subcube partitions of length $n$ and size $2n-1$.
In Section 2.4 we present several more such constructions which will be useful
in Section 3.

####  2.3.1 Lower bound

Before presenting the constructions of tight irreducible subcube partitions of
size $2n-1$, here is the best lower bound on the size, due to Kullmann and
Zhao [KZ16]. We give an alternative proof using known results from the
literature.

######  Theorem 2.14.

If $n\geq 4$ then every tight irreducible subcube partition of length $n$ has
size at least $n+3$.

Before proving the theorem, we need a simple lemma.

######  Definition 2.15 (Regularity).

A subcube partition of length $n$ is _regular_ if for every $i\in[n]$ and
every $b\in\\{0,1\\}$ there are at least two subcubes $s\in F$ such that
$s_{i}=b$.

This definition is due to Kullmann and Zhao [KZ13], who used the term
_nonsingular_. The term _regular_ appears in Peitl and Szeider [PS23].

######  Lemma 2.16 ([KZ16, Lemma 39]).

If $F$ is a tight irreducible subcube partition of length $n\geq 2$ then $F$
is regular.

###### Proof.

We prove the definition of regularity for $i=1$.

For $\sigma\in\\{0,1,*\\}$, let $F_{\sigma}=\\{x:\sigma x\in F\\}$. Both
$F_{0}\cup F_{*}$ and $F_{1}\cup F_{*}$ are subcube partitions of length
$n-1$, and so $\bigcup F_{0}=\bigcup F_{1}$. Since $F$ is tight, $F_{0},F_{1}$
are non-empty.

If $F_{0}=\\{x\\}$ and $|F_{1}|>1$ then the union of the subcubes
corresponding to $F_{1}$ is the subcube $1x$, contradicting irreducibility.

If $F_{0}=\\{x\\}$ and $|F_{1}|=1$ then $F_{0}=F_{1}=\\{x\\}$ and so the union
of the corresponding subcubes is $*x$. Since $F$ is irreducible, necessarily
$x=*^{n-1}$, and so $F=\\{0*^{n-1},1*^{n-1}\\}$. Since $F$ is tight,
necessarily $n=1$, contradicting the assumption $n\geq 2$.

It follows that $|F_{0}|\geq 2$. Similarly $|F_{1}|\geq 2$. ∎

We can now prove the size lower bound.

###### Proof of Theorem 2.14.

Let $F=\\{s_{1},\dots,s_{m}\\}$ be a tight subcube partition of length $n$. We
can identify $F$ with a formula $\Phi$ in _conjunctive normal form_ (CNF) over
variables $x_{1},\dots,x_{n}$ whose clauses are ‘‘$x\notin s_{i}$’’ for all
$i\in[m]$. For example, the subcube partition $0*,10,11$ corresponds to the
CNF $x_{1}\land(\bar{x}_{2}\lor x_{3})\land(\bar{x}_{2}\lor\bar{x}_{3})$.

Since every $x$ belongs to some $s_{i}$, the formula $\Phi$ is unsatisfiable.
It is moreover minimally unsatisfiable, meaning that if we remove any clause,
then it becomes satisfiable. Indeed, if we remove the clause ‘‘$x\notin
s_{i}$’’, then any point in $s_{i}$ would satisfy the formula. Since $F$ is
tight, $\Phi$ mentions all $n$ variables.

A well-known result attributed to Tarsi [AL86] states that a minimally
unsatisfiable CNF mentioning $n$ variables must contain at least $n+1$
clauses, hence $m\geq n+1$.

Suppose that $m=n+1$. Davydov, Davydova, and Kleine Büning [DDKB98, Theorem
12] showed that if a minimally unsatisfiable CNF mentioning $n$ variables
contains exactly $n+1$ clauses, then some variable appears once positively and
once negatively. In particular, $F$ is not regular, contradicting Lemma 2.16.
Hence $m\geq n+2$.

Suppose that $m=n+2$. Kleine Büning [KB00, Theorem 6] showed that there is a
unique regular minimally unsatisfiable CNF mentioning $n$ variables which
contains exactly $n+2$ clauses, up to renaming and reordering variables. The
collection of subcubes corresponding to this CNF consists of $0^{n},1^{n}$
together with all cyclic rotations of $10*^{n-2}$. When $n\geq 4$, these
subcubes are not disjoint: for example, $10*^{n-2}$ and $*^{2}10*^{n-4}$ both
contain the subcube $1010*^{n-4}$. Hence $m\geq n+3$. ∎

In the following two subsections, we present two constructions of the same
sequence of tight irreducible subcube partitions of length $n\geq 3$ and size
$2n-1$.

####  2.3.2 Merging

Our first construction is based on the following lemma, which is used to merge
together two subcube partitions.

######  Definition 2.17 (Reducibility for partial subcube partitions).

A subset $F^{\prime}$ of a subcube partition $F$ of length $n$ is _reducible_
if there exists a subset $G\subseteq F^{\prime}$, with $|G|>1$, such that the
union of the subcubes in $G$ is a subcube different from $*^{n}$.

######  Lemma 2.18.

Let $F_{0},F_{1}$ be two subcube partitions of length $n$. Let

$G=\\{0x:x\in F_{0}\setminus F_{1}\\}\cup\\{1x:x\in F_{1}\setminus
F_{0}\\}\cup\\{*x:x\in F_{0}\cap F_{1}\\}.$

Then

  1. (a)

$G$ is a subcube partition of length $n+1$.

  2. (b)

If $F_{0}\neq F_{1}$ and at least one of them is tight, then $G$ is tight.

  3. (c)

If $F_{0}\cap F_{1}\neq\emptyset$ and both $F_{0}\setminus F_{1}$ and $F_{1}$
are irreducible (or both $F_{1}\setminus F_{0}$ and $F_{0}$ are irreducible)
then $G$ is irreducible.

###### Proof.

The first two items follow easily from the construction (the condition
$F_{0}\neq F_{1}$ in the second item guarantees that the first coordinate is
mentioned).

Now suppose that $F_{0}\cap F_{1}\neq\emptyset$ and both $F_{0}\setminus
F_{1}$ and $F_{1}$ are irreducible. We need to show that $G$ is irreducible.
If not, then there is a subset $H\subset G$, with $1<|H|<|G|$, whose union is
a subcube $x\neq*^{n}$.

If $x=0y$ then $y$ is a union of $|H|$ subcubes in $F_{0}\setminus F_{1}$.
Since $F_{0}\setminus F_{1}$ is irreducible and $|H|>1$, necessarily
$y=*^{n}$. However, this contradicts the assumption $F_{0}\cap
F_{1}\neq\emptyset$.

We get a similar contradiction if $x=1y$, using the irreducibility of $F_{1}$.

Finally, if $x=*y$ then $y$ is a union of $|H|$ subcubes of $F_{0}$ as well as
a union of $|H|$ subcubes of $F_{1}$. Since $F_{1}$ is irreducible and
$y\neq*^{n}$, necessarily $y\in F_{1}$. If $y\in F_{0}$ then $x\in G$,
contradicting the assumption $|H|>1$. If $y\notin F_{0}$ then $1y\in G$ and so
$y$ is a union of subcubes in $F_{0}\setminus F_{1}$. Since $F_{0}\setminus
F_{1}$ is irreducible and $y\neq*^{n}$, necessarily $y\in F_{0}\setminus
F_{1}$, contradicting both $y\notin F_{0}$ and $y\in F_{1}$. ∎

We now construct the promised sequence of tight irreducible subcube
partitions.

######  Theorem 2.19.

For each $n\geq 3$ there is a tight irreducible subcube partition $S_{n}$ of
length $n$ and size $2n-1$.

###### Proof.

We construct the subcube partitions inductively. The starting point is

$S_{3}=\\{000,*01,1*0,01*,111\\},$

whose irreducibility was proved by Kullmann and Zhao [KZ16, Lemma 41], and can
also be checked using Algorithm 1. The construction will maintain the
invariants that $01*^{n-2}\in S_{n}$ and $1*^{n-1},00*^{n-2}\notin S_{n}$, and
moreover $|S_{n}|=2n-1$

Given $S_{n}$, we construct $S_{n+1}$ by applying Lemma 2.18 to
$F_{0}=\\{1*^{n-1},00*^{n-2},01*^{n-2}\\}$ and $F_{1}=S_{n}$.

Since $F_{0}$ is reducible and $F_{1}$ is irreducible, clearly $F_{0}\neq
F_{1}$, and so $S_{n+1}$ is tight by Lemma 2.18.

The invariant implies that $F_{0}\setminus F_{1}=\\{1*^{n-1},00*^{n-2}\\}$ is
irreducible. It follows that $S_{n+1}$ is irreducible by Lemma 2.18.

Since $1*^{n-1}\notin F_{1}$, it follows that $01*^{n-1}\in S_{n+1}$. Since
$0*^{n-1}\notin F_{0}$, it follows that $00*^{n-1}\notin S_{n+1}$. Since
$|F_{1}|>1$, in particular $*^{n}\notin F_{1}$, and so $1*^{n}\notin S_{n+1}$.

Finally, the invariants imply that $F_{0}\cap F_{1}=\\{01*^{n-2}\\}$, and so

$|S_{n+1}|=|F_{0}\setminus F_{1}|+|F_{1}\setminus F_{0}|+|F_{0}\cap
F_{1}|=2+(|F_{1}|-1)+1=2n+1,$

using $|F_{1}|=2n-1$. ∎

Here are the resulting subcube partitions for $n=3,4,5$:

$\displaystyle 000\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ $\displaystyle
000*\leavevmode\hbox to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip
0.0pt\lower 0.0pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ $\displaystyle
000**$ $\displaystyle 01*\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1000\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1000*$
$\displaystyle*01\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ $\displaystyle
01**\leavevmode\hbox to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip
0.0pt\lower 0.0pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}11000$ $\displaystyle
1*0\leavevmode\hbox to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip
0.0pt\lower 0.0pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}*01*\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ $\displaystyle
01***$ $\displaystyle 111\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1*01\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}*01**$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}11*0\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1*01*$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1111\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}11*01$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}111*0$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}11111$

####  2.3.3 Twisting

Our second construction starts with the observation

$x00\cup x1*=x*0\cup x11.$

Up to permutation and flipping of coordinates, this is the only way in which a
set of points can be written as a union of two subcubes in two different ways,
as we show below in Lemma 2.22. Following Kullmann and Zhao [KZ16, Definitions
45–46], we call such a pair of subcubes an _nfs-pair_. The _nfs-flip_ of the
pair on the left is the pair on the right.

######  Definition 2.20 (Nfs-pair, nfs-flip).

Two subcubes $s,t$ constitute an _nfs-pair_ if they differ on exactly two
positions $i,j$, where $(s_{i},t_{i})\in\\{(0,1),(1,0)\\}$ and $t_{j}=*$.

The _nfs-flip_ of $s,t$ is the pair of subcubes $s^{\prime},t^{\prime}$
obtained by copying the coordinates except for $i,j$, and setting
$s^{\prime}_{i}=*$, $s^{\prime}_{j}=s_{j}$, $t^{\prime}_{i}=t_{i}$,
$t^{\prime}_{j}=\bar{s}^{\prime}_{j}$.

######  Lemma 2.21.

If $s,t$ is an nfs-pair with nfs-flip $s^{\prime},t^{\prime}$ then $s\cup
t=s^{\prime}\cup t^{\prime}$.

Nfs-pairs are the only pairs of subcubes satisfying Lemma 2.21 non-trivially.

######  Lemma 2.22.

Let $s,t$ and $s^{\prime},t^{\prime}$ be two pairs of disjoint subcubes such
that $s\cup t=s^{\prime}\cup t^{\prime}$, the common value is not a subcube,
and $\\{s,t\\}\neq\\{s^{\prime},t^{\prime}\\}$. Then either $s,t$ or $t,s$ is
an nfs-pair, and $s^{\prime},t^{\prime}$ or $t^{\prime},s^{\prime}$ is its
nfs-flip.

###### Proof.

Since $s,t$ are disjoint, they must conflict. Without loss of generality,
$s=0p$ and $t=1q$. If both $s^{\prime}$ and $t^{\prime}$ start with non-stars
then clearly $\\{s,t\\}=\\{s^{\prime},t^{\prime}\\}$, and if both start with a
star then $p=q$ and so $s\cup t=*p$ is a subcube. Therefore without loss of
generality, $s^{\prime}=*p^{\prime}$ and $t^{\prime}=1q^{\prime}$.

Since $0p\cup 1q=*p^{\prime}\cup 1q^{\prime}$, considering the points starting
with $0$, we see that $p^{\prime}=p$. Considering the points starting with
$1$, we see that $q=p\cup q^{\prime}$. Since $p,q^{\prime},q$ are all
subcubes, it must be that $p,q^{\prime}$ are subcubes differing in a single
non-star position, and $q$ is obtained from them by changing this position to
a star. Thus $s,t$ is an nfs-pair, and $s^{\prime},t^{\prime}$ is its nfs-
flip. ∎

The construction is based on the following simple corollary of Lemma 2.18.

######  Lemma 2.23.

Let $F$ be a tight irreducible subcube partition containing an nfs-pair $s,t$,
and let $s^{\prime},t^{\prime}$ be its nfs-flip. The following subcube
partition is tight and irreducible, for any $b\in\\{0,1\\}$:

$G=\\{*x:x\in F,x\neq
s,t\\}\cup\\{bs,bt,\bar{b}s^{\prime},\bar{b}t^{\prime}\\}.$

Furthermore, $|G|=|F|+2$, and $G$ contains the nfs-pairs $bs,bt$ and
$\bar{b}s^{\prime},\bar{b}t^{\prime}$.

###### Proof.

Let $F^{\prime}$ be the formula obtained from $F$ by replacing $s,t$ with
$s^{\prime},t^{\prime}$. We apply Lemma 2.18 on $F_{b}=F$ and
$F_{\bar{b}}=F^{\prime}$, obtaining the stated subcube partition $G$.

Since $F\neq F^{\prime}$ and $F$ is tight, $G$ is tight.

Clearly $F$ cannot consist only of $s,t$, and so $F\cap
F^{\prime}\neq\emptyset$. Since $F$ and $F^{\prime}\setminus F\subset
F^{\prime}$ are both irreducible, it follows that $G$ is irreducible. ∎

In order to obtain the sequence $S_{n}$ constructed in Theorem 2.19 using
Lemma 2.23, start with $S_{3}$. Given $S_{n}$, apply the lemma with $s=1^{n}$,
$t=1^{n-2}*0$, and $b=1$, and rotate the resulting subcube partition once to
the left. The result is $S_{n+1}$. Here is an example:

$\displaystyle 000\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}*000\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}000*$ $\displaystyle
01*\leavevmode\hbox to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip
0.0pt\lower 0.0pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}*01*\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}01**$
$\displaystyle*01\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}**01\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}*01*$
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{1*0}\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}11*0\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1*01$
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{111}\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{1}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}0100\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1000$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}1111\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{1111}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}011*\leavevmode\hbox
to0pt{\vbox to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$
$\displaystyle\leavevmode\hbox to0pt{\vbox
to0pt{\pgfpicture\makeatletter\hbox{\hskip 0.0pt\lower 0.0pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}{}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{11*0}$

###  2.4 Minimal weight

In Section 3, we will consider irreducible subcube partitions over larger
alphabets. As we show in Section 3.1, one of the ways to construct an
irreducible subcube partition over an alphabet $\\{0,\dots,q-1\\}$ is to start
with an irreducible subcube partition over $\\{0,1\\}$, and replace each $1$
in each subcube with each of $\\{1,\ldots,q-1\\}$. The resulting number of
subcubes is

$\sum_{s\in F}(q-1)^{\\#_{1}(s)},$

where $F$ is the subcube partition we start with, and $\\#_{1}(s)$ is the
number of $1$s in $s$. This suggests looking for a tight irreducible subcube
partition which minimizes the above objective function.

The concept of _majorization_ allows us to optimize this objective function
for all $q$’s at once.

######  Definition 2.24 (Weight vector).

Let $F$ be a subcube partition of length $n$. Its _weight vector_ is the
vector $w(F)=w_{0},\dots,w_{n}$, where $w_{h}$ is the number of subcubes of
$F$ of _weight_ $h$, that is, with $h$ many $1$s.

The notation $w_{\geq h}$ stands for $w_{h}+\cdots+w_{n}$, which is the number
of subcubes with at least $h$ many $1$s.

######  Definition 2.25 (Majorization).

Let $a,b$ be two weight vectors of length $n+1$. We say that $a$ _majorizes_
$b$ if for every $h\leq n$, we have $a_{\geq h}\geq b_{\geq h}$.

######  Lemma 2.26.

Let $F,G$ be subcube partitions of length $n$. If $w(F)$ majorizes $w(G)$ then
for all monotone non-decreasing functions
$\phi\colon\\{0,\dots,n\\}\to\mathbb{R}$,

$\sum_{s\in F}\phi(\\#_{1}(s))\geq\sum_{s\in G}\phi(\\#_{1}(s)).$

In particular, this holds for $\phi(h)=(q-1)^{h}$ as long as $q\geq 2$.

###### Proof.

We will show that

$\sum_{h=0}^{n}w_{h}(F)\phi(h)\geq\sum_{h=0}^{n}w_{h}(G)\phi(h).$

Indeed,

$\displaystyle\sum_{h=0}^{n}w_{h}(F)\phi(h)$ $\displaystyle=w_{\geq
0}(F)\phi(0)+\sum_{h=1}^{n}w_{\geq h}(F)(\phi(h)-\phi(h-1))$
$\displaystyle\geq w_{\geq 0}(G)\phi(0)+\sum_{h=1}^{n}w_{\geq
h}(G)(\phi(h)-\phi(h-1))=\sum_{h=0}^{n}w_{h}(G)\phi(h).\qed$

Lemma 2.26 allows us to reformulate our goal: find the minimal weight vectors
(in the sense of majorization) of the tight irreducible subcube partitions of
length $n$. (There could be more than one minimal weight vector, since
majorization is not a linear order.)

######  Conjecture 2.

For every $n\geq 3$, the minimal weight vectors of tight irreducible subcube
partitions of length $n$ are $1,n-1,n-1,0,\dots,0$ and $1,n,n-3,1,0,\dots,0$.

In Section 2.4.1, we show that 1 implies the lower bound part of 2. In Section
2.4.2 we give matching constructions.

Unconditionally, we can show that every tight irreducible subcube partition of
length $n\geq 3$ must contain a subcube of weight $2$.

######  Lemma 2.27.

If $F$ is a tight irreducible subcube partition of length $n\geq 3$ then $F$
contains a subcube of weight at least $2$.

###### Proof.

Suppose that every subcube in $F$ has weight at most $1$. Let $s\in F$ be the
subcube containing $1^{n}$. If $s$ has weight $0$ then $s=*^{n}$,
contradicting the tightness of $F$. If $s$ has weight $1$ then, without loss
of generality, $s=1*^{n-1}$. The union of all other subcubes of $F$ must be
$0*^{n-1}$, and so by irreducibility, $F=\\{0*^{n-1},1*^{n-1}\\}$,
contradicting tightness. ∎

####  2.4.1 Lower bound

In this section we prove the lower bound part of 2, assuming 1. As we explain
in the proof, this amounts to ruling out the weight vector
$1,n,n-2,0,\dots,0$.

######  Theorem 2.28.

Assume 1. For every $n\geq 3$, the weight vector of any tight irreducible
subcube partition of length $n$ majorizes either $1,n-1,n-1,0,\dots,0$ or
$1,n,n-3,1,0,\dots,0$.

###### Proof.

Let $F$ be a tight irreducible subcube partition of length $n$, and let $w$ be
its weight vector. The theorem states that (i) $w_{\geq 0}\geq 2n-1$; (ii)
$w_{\geq 1}\geq 2n-2$; and either (iii) $w_{\geq 2}\geq n-1$ or (iv) $w_{\geq
2}\geq n-2$ and $w_{\geq 3}\geq 1$.

We start with the following observation: $w_{h}\leq\binom{n}{h}$. Indeed,
every subcube $s$ of weight $h$ contains the point $x_{s}$ obtained by
switching all $*$s to $0$s, which has weight $h$. Since the subcubes in $F$
are disjoint, every $s\in F$ of weight $h$ has a different $x_{s}$. Since
there are $\binom{n}{h}$ many possible $x_{s}$, it follows that
$w_{h}\leq\binom{n}{h}$.

The inequality $w_{\geq 0}\geq 2n-1$ is 1. Since $w_{0}\leq 1$, the inequality
$w_{\geq 1}\geq 2n-2$ follows. Since $w_{1}\leq n$, we deduce the inequality
$w_{\geq 2}\geq n-2$. To complete the proof, we need to show that either (iii)
$w_{\geq 2}\geq n-1$ or (iv) $w_{\geq 3}\geq 1$. We will show that the
assumptions $w_{\geq 2}=n-2$ and $w_{\geq 3}=0$ lead to a contradiction.

Suppose, therefore, that $w_{2}=n-2$ and $w_{\geq 3}=0$. Since $w_{\geq 0}\geq
2n-1$ and $w_{0}\leq 1$, $w_{1}\leq n$, this implies that $w_{0}=1$ and
$w_{1}=n$.

Since $w_{1}=n$, for every $i\in[n]$ there is a subcube $s^{(i)}\in F$ which
contains $1$ in the $i$’th position: $s^{(i)}_{i}=1$. The point $0^{n}$ is
covered by the unique subcube $s^{(0)}\in F$ of weight $0$. Since $s^{(0)}$
and $s^{(i)}$ must conflict, necessarily $s^{(0)}_{i}=0$ (this is the only
possible conflict), and so $s^{(0)}=0^{n}$ is a point.

Since $0^{n}\in F$, the subcubes $s^{(i)}$ cannot be points. Indeed, if
$s^{(i)}$ is a point then $s^{(i)}=0^{i-1}10^{n-i}$, and so $s^{(0)}\cup
s^{(i)}=0^{i-1}*0^{n-i}$, contradicting irreducibility. Consequently, all
points in $F$ have even weight, contradicting Lemma 2.12 (applied on the star
pattern $\emptyset$). ∎

####  2.4.2 Construction

In this section, we prove (unconditionally) the upper bound part of 2, by
constructing tight irreducible subcube partitions of length $n\geq 3$ and
weight vectors $1,n-1,n-1,0,\dots,0$ and $1,n,n-3,1,0,\dots,0$. The
constructions will use the method of Theorem 2.19. The same subcube partitions
can also be constructed using the method of Lemma 2.23; we leave the details
to the reader.

######  Theorem 2.29.

For each $n\geq 3$ there is a tight irreducible subcube partition $A_{n}$
whose weight vector is $1,n-1,n-1,0,\dots,0$.

###### Proof.

We construct the subcube partitions inductively, starting with

$A_{3}=\\{*00,001,01*,110,1*1\\},$

which is obtained from $S_{3}$ of Theorem 2.19 by flipping the third
coordinate. The construction will maintain the invariants that $01*^{n-2}\in
A_{n}$ and $1*^{n-1},00*^{n-2}\notin A_{n}$.

Given $A_{n}$, we construct $A_{n+1}$ by applying Lemma 2.18 to $F_{0}=A_{n}$
and $F_{1}=\\{1*^{n-1},00*^{n-2},01*^{n-2}\\}$, and rotating the result $G$
once to the left, that is, $A_{n+1}=\\{xb:bx\in G\\}$, where $b\in\\{0,1,*\\}$
and $x\in\\{0,1,*\\}^{n}$.

Since $F_{0}$ is irreducible and $F_{1}$ is reducible, clearly $F_{0}\neq
F_{1}$, and so $A_{n+1}$ is tight by Lemma 2.18.

The invariant implies that $F_{1}\setminus F_{0}=\\{1*^{n-1},00*^{n-2}\\}$ is
irreducible, and so $A_{n+1}$ is irreducible by Lemma 2.18.

The invariant states that $01*^{n-2}\in F_{0}$. Since $01*^{n-2}\in F_{1}$ by
definition, it follows that $*01*^{n-2}\in G$, and so $01*^{n-1}\in A_{n+1}$.
Since $A_{n+1}$ is irreducible, necessarily $00*^{n-1}\notin A_{n+1}$
(otherwise $00*^{n-1}\cup 01*^{n-1}=0*^{n}$ would be a subcube) and
$1*^{n}\notin A_{n+1}$ (otherwise the union of all other subcubes would be
$0*^{n}$).

Finally, the invariants imply that $F_{1}\setminus
F_{0}=\\{1*^{n-1},00*^{n-2}\\}$, and so compared to $F_{0}$, the subcube
partition $G$ gains one subcube of weight $2$ (namely, $11*^{n-1}$) and one
subcube of weight $1$ (namely, $100*^{n-2}$); all other subcubes originate
from $F_{0}$ and maintain their weight. ∎

######  Theorem 2.30.

For each $n\geq 3$ there is a tight irreducible subcube partition $D_{n}$
whose weight vector is $1,n,n-3,1,0,\dots,0$.

###### Proof.

The proof is very similar to that of Theorem 2.29. We take

$D_{3}=S_{3}=\\{*01,000,01*,111,1*0\\}.$

The rest of the proof is identical. ∎

The subcube partition $D_{3}$ is obtained from $A_{3}$ by flipping the third
coordinate, and this holds for every $n$, by construction. By flipping
coordinates appropriately, we can also obtain other tight irreducible subcube
partitions $B_{n},C_{n}$ whose weight vectors are $1,n-1,n-1,0,\dots,0$. The
subcube partition $B_{n}$ is obtained by flipping the first coordinate, and
$C_{n}$ is obtained by flipping both the first and the third coordinates. The
subcube partitions $B_{n},C_{n}$ can also be obtained using an iterative
construction as above.

Here are the subcube partitions $A_{5},B_{5},C_{5},D_{5}$ after rotation once
to the left:

$\begin{array}[]{clclclc}0000*&&0000*&&0100*&&0100*\\\
01000&&01001&&00001&&00000\\\ 0*100&&0*101&&0*101&&0*100\\\
0**10&&0**11&&0**11&&0**10\\\ 1***0&&1***1&&1***1&&1***0\\\
10001&&10000&&11000&&11001\\\ 1001&&*1000&&*0000&&*0001\\\
*101&&**100&&**100&&**101\\\ **11&&***10&&***10&&***11\\\\[5.0pt]
A_{5}&&B_{5}&&C_{5}&&D_{5}\end{array}$

Among all subcube partitions obtained from $A_{n}$ by flipping coordinates,
these are the only ones whose weight vector is either $1,n-1,n-1,0,\dots,0$ or
$1,n,n-3,1,0,\dots,0$.

###  2.5 Maximal number of points

In the following section, we tackle the problem of maximizing the number of
subcubes in an irreducible subcube partition. As a warm-up, we start with the
problem of maximizing the number of points (zero-dimensional subcubes) in an
irreducible subcube partition.

For $n=3,4,5,6$, a computer search reveals that the maximum number of points
in an irreducible subcube partition of length $n$ is $2,4,8,16$. This is
consistent with the following conjecture.

######  Conjecture 3.

If $n\geq 3$ then the maximum number of points in an irreducible subcube
partition of length $n$ is $2^{n-2}$.

It is easy to see that an irreducible subcube partition of length $n$ contains
at most $2^{n-1}$ points. Indeed, if the subcube partition contained more than
$2^{n-1}$ points then there would be two points differing in a single
coordinate. The union of these two points is an edge (a one-dimensional
subcube), contradicting irreducibility.

In the rest of this section, we construct an irreducible subcube partition of
length $n$ containing $2^{n-2}$ many points. The construction uses the
following lemma.

######  Lemma 2.31.

If $F\neq\\{0*^{n-1},1*^{n-1}\\}$ is an irreducible subcube partition of
length $n$ then the following is an irreducible subcube partition of length
$n+1$:

$G=\\{00t,11t:0t\in F\\}\cup\\{01t,10t:1t\in F\\}\cup\\{**t:*t\in F\\}.$

###### Proof.

Let $F^{\prime}$ be the irreducible subcube partition obtained from $F$ by
flipping the first coordinate. The subcube partition $G$ results from applying
Lemma 2.18 to $F$ and $F^{\prime}$. According to the lemma, in order to show
that $G$ is irreducible, it suffices to show that $F\cap
F^{\prime}\neq\emptyset$.

If $F\cap F^{\prime}=\emptyset$ then all subcubes in $F$ start with $0$ or
$1$. Hence the union of all subcubes in $F$ starting with $0$ is $0*^{n-1}$,
and the union of all subcubes in $F$ starting with $1$ is $1*^{n-1}$. Since
$F$ is irreducible, it follows that $F=\\{0*^{n-1},1*^{n-1}\\}$, contrary to
the assumption. Therefore $F\cap F^{\prime}\neq\emptyset$, completing the
proof. ∎

######  Corollary 2.32.

If $F\neq\\{0*^{n-1},1*^{n-1}\\}$ is an irreducible subcube partition of
length $n$ then for every $k\geq 1$, the following is an irreducible subcube
partition of length $n+k$:

$G=\\{a_{1}\ldots a_{k}t:bt\in
F,a_{1},\dots,a_{k},b\in\\{0,1\\},a_{1}\oplus\dots\oplus
a_{k}=b\\}\cup\\{*^{k}t:*t\in F\\}.$

###### Proof.

Apply the lemma iteratively $k-1$ times to $F$, noticing that the subcube
partition constructed in the lemma is never of the form $\\{0*^{m},1*^{m}\\}$.
∎

In order to construct an irreducible subcube partition of length $n$ with
$2^{n-2}$ many points, we apply the corollary to the irreducible subcube
partition $S_{3}$ from Theorem 2.19.

######  Theorem 2.33.

For every $n\geq 3$ there is an irreducible subcube partition of length $n$
containing $2^{n-2}$ many points.

###### Proof.

The subcube partition $S_{3}=\\{000,*01,1*0,01*,111\\}$ is irreducible
(according to Theorem 2.19) and contains two points. Applying Corollary 2.32
with $k=n-3$, we get an irreducible subcube partition of length $n$ in which
each of the two original points gives rise to $2^{n-3}$ points, for a total of
$2^{n-2}$ points. ∎

Using similar ideas, we can construct an irreducible subcube partition of
length $n$ containing any even number of points between $2$ and $2^{n-2}$. We
leave the details to the reader.

###  2.6 Maximal size

What is the maximal size of an irreducible subcube partition of length $n$?
Here are some values, based on experiments and an upper bound which we present
in Section 2.6.1:

$\begin{array}[]{r|ccccccc}n&3&4&5&6&7&8&9\\\ \hline\cr\text{Lower
bound}&5&9&20&40&80&160&320\\\ \text{Upper
bound}&5&9&20&40&83&166&334\end{array}$

Based on these results, we make the following conjecture.

######  Conjecture 4.

For every $n\geq 5$, the maximal size of an irreducible subcube partition of
length $n$ is $5\cdot 2^{n-3}$.

We give a matching construction in Section 2.4.2. The size $5\cdot 2^{n-3}$ is
best possible, assuming 3.

######  Lemma 2.34.

Assume 3. For every $n\geq 3$, every irreducible subcube partition of length
$n$ has size at most $5\cdot 2^{n-3}$.

###### Proof.

Let $F$ be an irreducible subcube partition of length $n$. According to 3, $F$
contains $m\leq 2^{n-2}$ points. All other subcubes of $F$ cover at least two
points, and so the size of $F$ is at most

$m+\frac{2^{n}-m}{2}=2^{n-1}+\frac{m}{2}\leq 2^{n-1}+2^{n-3}.\qed$

####  2.6.1 Upper bound

In this section, we use a result of Forcade [For73] to give an upper bound on
the size of irreducible subcube partitions.

######  Theorem 2.35.

For every $n\geq 3$, the size of any irreducible subcube partition of length
$n$ is at most

$\frac{2n-1}{3n-1}2^{n}=\left(\frac{16}{3}-\Theta\left(\frac{1}{n}\right)\right)2^{n-3}.$

###### Proof.

Let $F$ be an irreducible subcube partition of length $n$. Let $G$ be a
subcube partition obtained from $F$ by subdividing each subcube of dimension
larger than $1$ into edges (subcubes of dimension $1$) in an arbitrary way.

Since $F$ is irreducible, no two points in $G$ span an edge. Therefore the set
of edges in $G$ constitutes a maximal matching in the $n$-dimensional
hypercube. Forcade [For73] proved that any maximal matching in the
$n$-dimensional hypercube contains $m\geq\frac{n}{3n-1}2^{n}$ edges. Therefore

$|F|\leq|G|=m+(2^{n}-2m)=2^{n}-m\leq 2^{n}-\frac{n}{3n-1}2^{n}.\qed$

Forcade showed that the bound $\frac{n}{3n-1}2^{n}$ is asymptotically tight by
giving a matching construction. Therefore this method cannot prove the
conjectured upper bound $5\cdot 2^{n-3}$.

####  2.6.2 Construction

In this section we construct irreducible subcube partitions of size $5\cdot
2^{n-3}$ for all $n\geq 3$ except for $n=4$. When $n=4$, a computer search
reveals that the maximum number of subcubes is $9$, which is achieved by

$0000,0011,1101,1110,*100,*111,0*01,0*10,10**.$

We prove this below.

Our construction is based on the work of Perezhogin [Per05], brought to our
attention by Tarannikov [Tar23].111The construction on page 55 in [Per05]
contains several minor errors. Tarannikov pointed out to us that the
definition of the $M_{\sigma_{i}\sigma_{j}}^{n+2}$ there should read
$\displaystyle M_{00}^{n+2}=(M_{00}^{n}(00)\cup M_{01}^{n}(01)\cup
M_{11}^{n}(11)\cup
M_{10}^{n}(10)\cup\mathbf{v}_{1}^{00}\cup\mathbf{v}_{2}^{00}\cup\mathbf{v}_{3}^{00}\cup\mathbf{v}_{4}^{00})\setminus(\mathbf{e}_{1}(00)\cup\mathbf{e}_{2}(01)\cup\mathbf{e}_{3}(11)\cup\mathbf{e}_{4}(10)),$
$\displaystyle M_{01}^{n+2}=(M_{00}^{n}(01)\cup M_{01}^{n}(11)\cup
M_{11}^{n}(10)\cup
M_{10}^{n}(00)\cup\mathbf{v}_{1}^{01}\cup\mathbf{v}_{2}^{10}\cup\mathbf{v}_{3}^{01}\cup\mathbf{v}_{4}^{10})\setminus(\mathbf{e}_{1}(01)\cup\mathbf{e}_{2}(11)\cup\mathbf{e}_{3}(10)\cup\mathbf{e}_{4}(00)),$
$\displaystyle M_{11}^{n+2}=(M_{00}^{n}(11)\cup M_{01}^{n}(10)\cup
M_{11}^{n}(00)\cup
M_{10}^{n}(01)\cup\mathbf{v}_{1}^{11}\cup\mathbf{v}_{2}^{11}\cup\mathbf{v}_{3}^{11}\cup\mathbf{v}_{4}^{11})\setminus(\mathbf{e}_{1}(11)\cup\mathbf{e}_{2}(10)\cup\mathbf{e}_{3}(00)\cup\mathbf{e}_{4}(01)),$
$\displaystyle M_{10}^{n+2}=(M_{00}^{n}(10)\cup M_{01}^{n}(00)\cup
M_{11}^{n}(01)\cup
M_{10}^{n}(11)\cup\mathbf{v}_{1}^{10}\cup\mathbf{v}_{2}^{01}\cup\mathbf{v}_{3}^{10}\cup\mathbf{v}_{4}^{01})\setminus(\mathbf{e}_{1}(10)\cup\mathbf{e}_{2}(00)\cup\mathbf{e}_{3}(01)\cup\mathbf{e}_{4}(11)).$
The construction is inductive, increasing the length by $2$ at each step.
Consequently, we will need two base cases, for $n=3$ and for $n=6$. The same
inductive construction will also be used in Section 2.8 to construct subcube
partitions consisting only of edges for all $n\geq 4$ except for $n=5$.

We start with the inductive step. The construction uses a mapping from
$\mathbb{Z}_{4}$ to $\\{0,1\\}^{2}$:

$\begin{array}[]{cccc}0&1&2&3\\\ \hline\cr 00&01&11&10\end{array}$

From a geometric perspective, we enumerate vertices of a two-dimensional face
clockwise:

0 00 1 01 2 11 3 10 $0*$ $*1$ $1*$ $*0$

We denote this mapping, known as the _Gray map_ , by
$\alpha\mapsto\llbracket{\alpha}\rrbracket$. We use the same notation to
associate two adjacent elements of $\mathbb{Z}_{4}$ with the corresponding
edge, e.g. $\llbracket{1,2}\rrbracket=*1$.

Let $\mathbb{W}_{4}$ consist of all subsets of $\mathbb{Z}_{4}$ which are
either singletons or pairs of adjacent elements. The function
$\phi\mapsto\llbracket{\phi}\rrbracket$ maps $\mathbb{W}_{4}$ into
$\\{0,1,*\\}^{2}\setminus\\{**\\}$. Given $\phi\in\mathbb{W}_{4}$ and
$\alpha\in\mathbb{Z}_{4}$, we define $\phi+\alpha$ in the obvious way. For
example, $\\{1\\}+2=\\{3\\}$ and $\\{1,2\\}+2=\\{3,0\\}=\\{0,3\\}$.

The construction will apply to subcube partitions which satisfy the following
_complementation property_.

######  Definition 2.36 (Complementation property).

A subcube partition $F$ of length $n\geq 2$ satisfies the _complementation
property_ if the following properties hold:

  1. (a)

No subcube in $F$ ends with $**$.

  2. (b)

If $s\llbracket{\phi}\rrbracket\in F$, where $\phi\in\mathbb{W}_{4}$, then
$s\llbracket{\phi+2}\rrbracket\notin F$.

(Note that $\llbracket{\alpha+2}\rrbracket$ is obtained from
$\llbracket{\alpha}\rrbracket$ by complementing both symbols, leaving stars
untouched.)

The construction is given by the following lemma.

######  Lemma 2.37.

Let $F$ be an irreducible subcube partition of length $n\geq 2$ containing
$0^{n-2}\llbracket{0,1}\rrbracket$ and satisfying the complementation
property. Define

$F^{\prime}=\\{s\llbracket{\phi-\alpha}\rrbracket\llbracket{\alpha}\rrbracket:s\llbracket{\phi}\rrbracket\in
F,\alpha\in\mathbb{Z}_{4},s\llbracket{\alpha}\rrbracket\neq
0^{n-2}\llbracket{0,1}\rrbracket\\}\cup\\{0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha,\alpha+1}\rrbracket:\alpha\in\mathbb{Z}_{4}\\}.$

Then $F^{\prime}$ is a tight irreducible subcube partition of length $n+2$
containing $0^{n}\llbracket{0,1}\rrbracket$ and satisfying the complementation
property. Moreover, for every $d$, if $F$ contains $m$ subcubes of dimension
$d$ then $F^{\prime}$ contains $4m$ subcubes of dimension $d$.

###### Proof.

We can write $F^{\prime}$ as follows:

$F^{\prime}=\underbrace{\\{s\llbracket{\phi-\alpha}\rrbracket\llbracket{\alpha}\rrbracket:s\llbracket{\phi}\rrbracket\in
F\\}}_{F^{\prime\prime}}\setminus\underbrace{\\{0^{n-2}\llbracket{\alpha,\alpha+1}\rrbracket\llbracket{-\alpha}\rrbracket\\}}_{\text{removed
edges}}\cup\underbrace{\\{0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha,\alpha+1}\rrbracket\\}}_{\text{added
edges}},$

where $\alpha$ ranges over $\mathbb{Z}_{4}$. We use the terms ‘‘removed
edges’’ and ‘‘added edges’’ below to refer to the sets in the expression
above.

Most of the properties (apart from irreducibility) are easy to verify:

Subcube partition

The removed edges and the added edges cover the same set of points, namely

$\\{0^{n-2}\llbracket{\alpha}\rrbracket\llbracket{\beta}\rrbracket:\alpha+\beta\in\\{0,1\\}\\},$

and so $F^{\prime}$ is a subcube partition.

Tightness

The added edges $0^{n-2}\llbracket{0}\rrbracket\llbracket{0,1}\rrbracket$ and
$0^{n-2}\llbracket{3}\rrbracket\llbracket{1,2}\rrbracket$ together mention all
coordinates.

Contains $0^{n}\llbracket{0,1}\rrbracket$

This is one of the added edges.

Complementation property

By construction, no subcube in $F^{\prime}$ ends with $**$. It remains to show
that if $t\llbracket{\psi}\rrbracket\in F^{\prime}$ then
$t\llbracket{\psi+2}\rrbracket\notin F^{\prime}$. If $\psi$ is a pair then
$t\llbracket{\psi}\rrbracket$ is one of the added edges, and each of these has
a different $t$.
If $\psi=\\{\alpha\\}$ is a singleton then
$t\llbracket{\psi}\rrbracket=s\llbracket{\phi-\alpha}\rrbracket\llbracket{\alpha}\rrbracket$
for some $s\llbracket{\phi}\rrbracket\in F$. If $F^{\prime}$ also contains
$t\llbracket{\psi+2}\rrbracket=s\llbracket{\phi-\alpha}\rrbracket\llbracket{\alpha+2}\rrbracket$
then $s\llbracket{\phi+2}\rrbracket\in F$, contradicting the assumption that
$F$ satisfies the complementation property.

Subcube counts

Since $\llbracket{\phi+\alpha}\rrbracket$ has the same number of stars as
$\llbracket{\phi}\rrbracket$ and $\llbracket{\alpha}\rrbracket$ has no stars,
each subcube in $F$ gives rise to four subcubes of the same dimension in
$F^{\prime\prime}$. Getting from $F^{\prime\prime}$ to $F^{\prime}$ involved
adding and removing four edges, hence the claim about subcube counts.

##### Irreducibility

The main part of the proof is proving the irreducibility of $F^{\prime}$. Let
$G^{\prime}$ be a non-empty set whose union is a subcube. We need to show that
either $|G^{\prime}|=1$ or $G^{\prime}=F^{\prime}$.

For every $\alpha\in\mathbb{Z}_{4}$, define

$\displaystyle G_{\alpha}$
$\displaystyle=\\{s\llbracket{\phi}\rrbracket:s\llbracket{\phi-\alpha}\rrbracket\llbracket{\alpha}\rrbracket\in
G^{\prime}\\},$ $\displaystyle H_{\alpha}$
$\displaystyle=\\{s\llbracket{\phi-\alpha}\rrbracket:s\llbracket{\phi-\alpha}\rrbracket\llbracket{\alpha}\rrbracket\in
G^{\prime}\\},$ $\displaystyle P_{\alpha}$
$\displaystyle=\\{t\in\\{0,1\\}^{n}:t\llbracket{\alpha}\rrbracket\in\bigcup
G^{\prime}\\}.$

By construction, $G_{\alpha}\subseteq
F\setminus\\{0^{n-2}\llbracket{0,1}\rrbracket\\}$.

We consider several cases, according to which added edges (if any) belong to
$G^{\prime}$.

##### No added edges

Suppose first that $G^{\prime}$ contains no added edge. In this case,

$G^{\prime}=\bigcup_{\alpha}\\{t\llbracket{\alpha}\rrbracket:t\in
H_{\alpha}\\}.$

This implies that $\bigcup H_{\alpha}$, and so $\bigcup G_{\alpha}$, are
subcubes of $F$ for each $\alpha$. By irreducibility of $F$, each $G_{\alpha}$
is either empty or a singleton.

If there is a single non-empty $H_{\alpha}$ then $G^{\prime}$ is a singleton,
and we are done. Suppose therefore that at least two $H_{\beta}$ are non-
empty. If $H_{\alpha},H_{\alpha+2}$ are non-empty then since
$\llbracket{\alpha}\rrbracket\lor\llbracket{\alpha+2}\rrbracket=**$, in fact
$H_{\beta}$ is non-empty for all $\beta$. Therefore we can assume that
$H_{\alpha},H_{\alpha+1}$ are non-empty for some $\alpha$.

Suppose $H_{\alpha}=\\{s\llbracket{\phi-\alpha}\rrbracket\\}$, where
$s\llbracket{\phi}\rrbracket\in F$. Since $\bigcup G^{\prime}$ is a subcube,
we have $\bigcup H_{\alpha}=\bigcup H_{\alpha+1}$. Recalling that
$H_{\alpha+1}$ is a singleton, this shows that
$s\llbracket{\phi-\alpha}\rrbracket\in H_{\alpha+1}$, and so
$s\llbracket{\phi+1}\rrbracket\in F$. Thus
$s\llbracket{\phi}\rrbracket,s\llbracket{\phi+1}\rrbracket\in F$.

If $\phi=\\{\alpha\\}$ then $s\llbracket{\alpha}\rrbracket\cup
s\llbracket{\alpha+1}\rrbracket=s\llbracket{\alpha,\alpha+1}\rrbracket$,
contradicting the irreducibility of $F$. If $\phi=\\{\alpha,\alpha+1\\}$, then
$s\llbracket{\phi}\rrbracket\cap
s\llbracket{\phi+1}\rrbracket=s\llbracket{\alpha+1}\rrbracket$, contradicting
the assumption that $F$ is a partition. Therefore this case cannot happen.

##### Single added edge

Suppose next that $G^{\prime}$ contains a single added edge,
$0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha,\alpha+1}\rrbracket$.
Then

$\displaystyle P_{\alpha}$ $\displaystyle=\bigcup
H_{\alpha}\cup\\{0^{n-2}\llbracket{-\alpha}\rrbracket\\},$
$\displaystyle\bigcup G_{\alpha}$
$\displaystyle=\\{s\llbracket{\beta+\alpha}\rrbracket:s\llbracket{\beta}\rrbracket\in
P_{\alpha},s\llbracket{\beta}\rrbracket\neq
0^{n-2}\llbracket{-\alpha}\rrbracket\\}$
$\displaystyle=\\{s\llbracket{\beta+\alpha}\rrbracket:s\llbracket{\beta}\rrbracket\in
P_{\alpha}\\}\setminus\\{0^{n-2}\llbracket{0}\rrbracket\\},$ $\displaystyle
P_{\alpha+1}$ $\displaystyle=\bigcup
H_{\alpha+1}\cup\\{0^{n-2}\llbracket{-\alpha}\rrbracket\\},$
$\displaystyle\bigcup G_{\alpha+1}$
$\displaystyle=\\{s\llbracket{\beta+\alpha+1}\rrbracket:s\llbracket{\beta}\rrbracket\in
P_{\alpha+1},s\llbracket{\beta}\rrbracket\neq
0^{n-2}\llbracket{-\alpha}\rrbracket\\}$
$\displaystyle=\\{s\llbracket{\beta+\alpha+1}\rrbracket:s\llbracket{\beta}\rrbracket\in
P_{\alpha+1}\\}\setminus\\{0^{n-2}\llbracket{1}\rrbracket\\}.$

Since $\bigcup G^{\prime}$ is a subcube, we have $P_{\alpha}=P_{\alpha+1}$,
and the common value is a subcube containing
$0^{n-2}\llbracket{-\alpha}\rrbracket$. We claim that this subcube must be of
the form $r\llbracket{-\alpha}\rrbracket$. This is because of the following:

  * •

Since $0^{n-2}\llbracket{0,1}\rrbracket\in F$, in particular
$0^{n-2}\llbracket{1}\rrbracket\notin F$, and so
$0^{n-2}\llbracket{1-\alpha}\rrbracket\notin P_{\alpha}$.

  * •

By assumption $G^{\prime}$ doesn’t contain the added edge
$0^{n-2}\llbracket{-\alpha-1}\rrbracket\llbracket{\alpha+1,\alpha+2}\rrbracket$,
and so $0^{n-2}\llbracket{-\alpha-1}\rrbracket\notin P_{\alpha+1}=P_{\alpha}$.

  * •

Since $\llbracket{-\alpha}\rrbracket\lor\llbracket{2-\alpha}\rrbracket=**$,
also $0^{n-2}\llbracket{2-\alpha}\rrbracket\notin P_{\alpha}$ (otherwise
$P_{\alpha}$ would contain $0^{n-2}**$ since $P_{\alpha}$ is a subcube).

Notice now that

$\bigcup(G_{\alpha}\cup G_{\alpha+1}\cup
0^{n-2}\llbracket{0,1}\rrbracket)=\\{s\llbracket{\beta+\alpha}\rrbracket,s\llbracket{\beta+\alpha+1}\rrbracket:s\llbracket{\beta}\rrbracket\in
P_{\alpha}\\}=r\llbracket{0,1}\rrbracket.$

The irreducibility of $F$ implies that
$r\llbracket{0,1}\rrbracket=0^{n-2}\llbracket{0,1}\rrbracket$. Therefore
either $\bigcup
G^{\prime}=0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha,\alpha+1}\rrbracket$
or $\bigcup G^{\prime}=0^{n-2}\llbracket{-\alpha}\rrbracket**$. In the former
case, $G^{\prime}$ is a singleton consisting just of a single added edge, and
so it remains to rule out the latter case.

If $\bigcup G^{\prime}=0^{n-2}\llbracket{-\alpha}\rrbracket**$ then in
particular
$0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha+2,\alpha+3}\rrbracket\subseteq\bigcup
G^{\prime}$, and so $\bigcup
H_{\alpha+2}=0^{n-2}\llbracket{-\alpha}\rrbracket$ and $\bigcup
H_{\alpha+3}=0^{n-2}\llbracket{-\alpha}\rrbracket$. This implies that $\bigcup
G_{\alpha+2}=0^{n-2}\llbracket{2}\rrbracket$ and $\bigcup
G_{\alpha+3}=0^{n-2}\llbracket{3}\rrbracket$, and so both
$0^{n-2}\llbracket{2}\rrbracket,0^{n-2}\llbracket{3}\rrbracket\in F$. However,
this contradicts the irreducibility of $F$, since
$0^{n-2}\llbracket{2}\rrbracket\cup
0^{n-2}\llbracket{3}\rrbracket=0^{n-2}\llbracket{2,3}\rrbracket$ is a subcube.

##### Exactly two adjacent added edges

Suppose now that $G^{\prime}$ contains precisely two added edges, whose
indices differ by $1$, say
$0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha,\alpha+1}\rrbracket$
and
$0^{n-2}\llbracket{-\alpha-1}\rrbracket\llbracket{\alpha+1,\alpha+2}\rrbracket$.
Therefore

$P_{\alpha+1}=\bigcup
H_{\alpha+1}\cup\\{0^{n-2}\llbracket{-\alpha-1,-\alpha}\rrbracket\\},$

which implies that

$\bigcup
G_{\alpha+1}=\\{s\llbracket{\beta+\alpha+1}\rrbracket:s\llbracket{\beta}\rrbracket\in
P_{\alpha+1}\\}\setminus\\{0^{n-2}\llbracket{0,1}\rrbracket\\}.$

Since $\bigcup G^{\prime}$ is a subcube, also $P_{\alpha+1}$ is a subcube, and
so $\bigcup(G_{\alpha+1}\cup 0^{n-2}\llbracket{0,1}\rrbracket)$ is a subcube.
The irreducibility of $F$ implies that $G_{\alpha+1}=\emptyset$, and so
$P_{\alpha+1}=0^{n-2}\llbracket{-\alpha-1,-\alpha}\rrbracket$.

The join of the two added edges is
$0^{n-2}\llbracket{-\alpha-1,-\alpha}\rrbracket**$, and this shows that all
$P_{\beta}$ are equal. In particular, since $P_{\alpha}=\bigcup
H_{\alpha}\cup\\{0^{n-2}\llbracket{-\alpha}\rrbracket\\}$, we have
$H_{\alpha}=\\{0^{n-2}\llbracket{-\alpha-1}\rrbracket\\}$ and so
$G_{\alpha}=\\{0^{n-2}\llbracket{3}\rrbracket\\}$. Similarly,
$P_{\alpha+2}=\bigcup
H_{\alpha+2}\cup\\{0^{n-2}\llbracket{-\alpha-1}\rrbracket\\}$ and so
$H_{\alpha+2}=\\{0^{n-2}\llbracket{-\alpha}\rrbracket\\}$, implying that
$G_{\alpha+2}=\\{0^{n-2}\llbracket{2}\rrbracket\\}$. However, then
$0^{n-2}\llbracket{2}\rrbracket,0^{n-2}\llbracket{3}\rrbracket\in F$, which
contradicts the irreducibility of $F$ since
$0^{n-2}\llbracket{2}\rrbracket\cup
0^{n-2}\llbracket{3}\rrbracket=0^{n-2}\llbracket{2,3}\rrbracket$ is a subcube.

##### Two non-adjacent added edges

In the remaining case, the set $G^{\prime}$ contains two non-adjacent edges,
say
$0^{n-2}\llbracket{-\alpha}\rrbracket\llbracket{\alpha,\alpha+1}\rrbracket$
and
$0^{n-2}\llbracket{-\alpha-2}\rrbracket\llbracket{\alpha+2,\alpha+3}\rrbracket$.
The join of these two edges is $0^{n-2}****$, and so $\bigcup G^{\prime}$ is a
subcube ending with $****$. In particular, $G^{\prime}$ must contain all added
edges.

Let $G^{\prime\prime}$ be obtained from $G^{\prime}$ by replacing the added
edges with the removed edges. Since the added edges and the removed edges span
the same points, $\bigcup G^{\prime\prime}$ is still a subcube. Consider

$G^{\prime\prime}_{0}=\\{s\llbracket{\phi}\rrbracket:s\llbracket{\phi}\rrbracket\llbracket{0}\rrbracket\in
G^{\prime\prime}\\}\subseteq F.$

Since $\bigcup G^{\prime\prime}_{0}$ is a subcube, the irreducibility of $F$
implies that either $G^{\prime\prime}_{0}$ is a singleton or $\bigcup
G^{\prime\prime}_{0}=\\{0,1\\}^{n}$. In the latter case, clearly $\bigcup
G^{\prime}=\\{0,1\\}^{n+2}$, and so $G^{\prime}=F^{\prime}$. In the former
case, since the removed edge $0^{n-2}\llbracket{0,1}\rrbracket$ belongs to
$G^{\prime\prime}_{0}$ by construction, we see that
$G^{\prime\prime}_{0}=\\{0^{n-2}\llbracket{0,1}\rrbracket\\}$. However, since
$\bigcup G^{\prime\prime}$ is a subcube ending with $****$, we see that
$\bigcup G^{\prime\prime}_{0}$ should be a subcube ending with $**$ rather
than with $\llbracket{0,1}\rrbracket$. So this case cannot happen. ∎

We can now construct the desired subcube partitions.

######  Theorem 2.38.

For every $n\geq 3$ other than $n=4$ there is a tight irreducible subcube
partition of length $n$ and size $5\cdot 2^{n-3}$.

###### Proof.

Using Lemma 2.37, it suffices to construct tight irreducible subcube
partitions of lengths $n\in\\{3,6\\}$ containing $0^{n-1}*$ and satisfying the
complementation property in the lemma.

For $n=3$, we can take

$100,*10,1*1,00*,011.$

For $n=6$, we can take

$\displaystyle\mathit{abcdef}\colon a\oplus b=c\oplus f=\overline{d\oplus e}$
$\displaystyle*aba\bar{b}\bar{a}$ $\displaystyle a*\bar{a}b\bar{a}b$
$\displaystyle ab*\bar{b}\bar{a}b$ $\displaystyle ab\bar{a}*ab$ $\displaystyle
aba\bar{b}*\bar{b}$ $\displaystyle ababa*$

Here $a,b,c,d,e,f$ range over $\\{0,1\\}$. ∎

We close this section by showing that $n=4$ is indeed exceptional. We first
need the following lemma, which will also be useful in Section 2.8.

######  Lemma 2.39.

Let $F$ be an irreducible subcube partition of length $4$. The set of points
in $F$ is either empty or one of the following, up to permutation and flipping
of coordinates:

$\displaystyle 0000$ $\displaystyle 0000$ $\displaystyle 1110$ $\displaystyle
1110$ $\displaystyle 1101$ $\displaystyle 0011$

###### Proof.

Suppose that $F$ contains a point, say $0000\in F$. According to Lemma 2.12,
$F$ must contain a point of odd parity. Due to irreducibility, this point
needs to have weight $3$, say $1110\in F$.

If $|F|>2$ then according to Lemma 2.12, $F$ contains another point of odd
parity, which due to irreducibility needs to have weight $3$, say $1101\in F$.
According to Lemma 2.12, $F$ needs to contain another point of even parity,
which due to irreducibility cannot be one of $1100,1010,0110,1001,0101,1111$.
Therefore $0011\in F$.

Due to irreducibility, $1011,0111\notin F$, and so Lemma 2.12 shows that in
this case $F$ contains precisely the following points: $0000,1110,1101,0011$.
∎

We can now show that Theorem 2.38 cannot hold for $n=4$.

######  Lemma 2.40.

There is no irreducible subcube partition of length $4$ and size $10$.

###### Proof.

Let $F$ be an irreducible subcube partition of length $4$ and size $10$.
According to Lemma 2.39, $F$ contains at most $4$ points, and so has to
consist of $4$ points and $6$ edges. Moreover, without loss of generality the
points in $F$ are $0000,1110,1101,0011$.

Let $F_{i}$ consist of all subcubes $s\in F$ with $s_{i}=*$. Note that $F_{i}$
is non-empty, since otherwise the union of subcubes $s\in F$ with $s_{i}=0$ is
$*^{i-1}0*^{4-i}$, contradicting irreducibility.

There are exactly two points in $F$ belonging to $*^{i-1}0*^{4-i}$. Each edge
outside of $F_{i}$ contains an even number of such points, and each edge in
$F_{i}$ contains one such point. Therefore $|F_{i}|$ is even, and so
$|F_{i}|\geq 2$. This implies that $|F_{1}|+|F_{2}|+|F_{3}|+|F_{4}|\geq 8$,
contradicting the fact that $F$ contains only $6$ edges. ∎

This lemma also follows from the computation of Peitl and Szeider [PS23, Table
1].

###  2.7 Maximal minimum dimension

All irreducible subcube partitions we have exhibited so far contain points. Is
this necessary? More generally, given $n$, what is the maximal $d$ such that
there exists a tight irreducible subcube partition in which every subcube has
dimension at least $d$? (The question doesn’t make sense without assuming
tightness, since $*^{n}$ is always irreducible.)

The constructions we give below suggest the following conjecture.

######  Definition 2.41 (Minimum dimension).

For a subcube partition $F$, let $\delta(F)$ denote the minimum dimension of a
subcube of $F$.

Also, let $\delta_{*}(F)$ denote the minimum dimension of a subcube of $F$
ending with a star (if such a subcube exists), and let $\delta_{b}(F)$ denote
the minimum dimension of a subcube of $F$ not ending with a star (if such a
subcube exists).

######  Conjecture 5.

Every tight irreducible subcube partition $F$ of length $n$ satisfies
$\delta(F)\leq n/2-o(n)$.

One can similarly ask for the maximum value of $\Delta(F)$, which is the
minimum codimension of a subcube of $F$, over all irreducible subcube
partitions of length $n$. The results in Section 2.6 shows that when $n\geq 3$
the maximal value is $\Delta(F)=n-1$ (the case $n=4$ is covered in Section
2.8).

In the remainder of this section, we give a construction matching 5. The
construction is based on the following lemma.

######  Lemma 2.42.

Let $F$ be a subcube partition of length $n$. Define

$G=\\{*t**:t*\in F\\}\cup\\{0tb*,1t*b:b\in\\{0,1\\},tb\in F\\}.$

Then

  1. (a)

$G$ is a subcube partition of length $n+2$.

  2. (b)

If $F$ is tight then $G$ is tight.

  3. (c)

If $F$ is irreducible and contains a subcube ending with a star then $G$ is
irreducible and contains a subcube ending with a star.

  4. (d)

We have $\delta_{*}(G)=\min(\delta_{*}(F)+2,\delta_{b}(F)+1)$ and
$\delta_{b}(G)=\delta_{b}(F)+1$, and so $\delta(G)\geq\delta(F)+1$. Moreover,
if $\delta(F)=\delta_{b}(F)$ then
$\delta(G)=\delta_{*}(G)=\delta_{b}(G)=\delta(F)+1$.

###### Proof.

Let $F_{0}=\\{tc*:tc\in F\\}$ and $F_{1}=\\{t*c:tc\in F\\}$, where
$c\in\\{0,1,*\\}$ in both cases. Applying Lemma 2.18 to $F_{0},F_{1}$, we
obtain the subcube partition $G$.

Suppose that $F$ is tight. For every $i\in\\{1,\dots,n-1\\}$, some subcube of
$F$ mentions coordinate $i$. The corresponding subcube or subcubes of $G$
mention coordinate $i+1$. Some subcube of $F$ mentions coordinate $n$. The
corresponding subcubes of $G$ mention the remaining coordinates $1,n+1,n+2$.

Suppose that $F$ is irreducible and contains a subcube $s\in F$ ending with a
star. The irreducibility of $F$ directly implies the irreducibility of $F_{0}$
and $F_{1}$. Since $s*\in F_{0}\cap F_{1}$, Lemma 2.18 implies that $G$ is
irreducible. Furthermore, $*s*\in G$ is a subcube ending with a star.

The remaining claims are easy to verify directly once we notice that the
dimension of a subcube is the number of star coordinates. ∎

We apply the construction on three specific tight irreducible subcube
partitions (one only for $n=4$) in order to obtain the following result, which
gives the best constructions we are aware of.

######  Theorem 2.43.

For every odd $n\geq 3$ there is a tight irreducible subcube partition $F$ of
length $n$ with $\delta(F)=\frac{n-3}{2}$.

For $n=4$ there is a tight irreducible subcube partition $F$ of length $n$
with $\delta(F)=\frac{n-4}{2}$.

For every even $n\geq 6$ there is a tight irreducible subcube partition $F$ of
length $n$ with $\delta(F)=\frac{n-2}{2}$.

###### Proof.

The first part follows from applying Lemma 2.42 to the tight irreducible
subcube partition $S_{3}$ of Theorem 2.19. The second part follows from taking
the tight irreducible subcube partition $S_{4}$ of the same theorem. The third
part follows from applying Lemma 2.42 to the following tight irreducible
subcube partition, whose irreducibility can be checked using Algorithm 1:

$\displaystyle 0*0*1*$ $\displaystyle 00**0*$ $\displaystyle 001*1*$
$\displaystyle 010*0*$ $\displaystyle 0110**$ $\displaystyle 1**0*1$
$\displaystyle 10***0$ $\displaystyle 10*1*1$ $\displaystyle 11*0*0$
$\displaystyle 1101**$ $\displaystyle*111**\qed$

###  2.8 Homogeneous subcube partitions

So far we have considered various parameters of irreducible subcube
partitions, attempting to optimize them. The final question we consider
concerns subcube partitions in which all subcubes have the same codimension.

######  Definition 2.44 (Homogeneity).

An _( $n,k)$-homogeneous_ subcube partition is a tight subcube partition of
length $n$ in which all subcubes have codimension $k$.

In this section, we explore the following question: for which $n,k$ does there
exist an irreducible $(n,k)$-homogeneous subcube partition?

Here is a table with some experimental results:

$\begin{array}[]{c|cccccc}&n=4&n=5&n=6&n=7&n=8&n=9\\\ \hline\cr
k=3&\checkmark&\times&\times&\times&\times&\times\\\
k=4&&\times&\checkmark&\times&\times&\times\\\
k=5&&&\checkmark&\checkmark&\checkmark&\checkmark\\\
k=6&&&&\checkmark&\checkmark&\checkmark\\\ k=7&&&&&\checkmark&\checkmark\\\
k=8&&&&&&\checkmark\end{array}$

In Section 2.8.1 we prove several elementary results: an irreducible
$(n,1)$-homogeneous subcube partition exists only for $n=1$; no irreducible
$(n,2)$-homogeneous partition exists; and for $k\geq 3$, if an irreducible
$(n,k)$-homogeneous subcube partition exists then $k+1\leq n\leq 2^{k}-3$. In
Section 2.8.2 we show that the weight distribution of an $(n,k)$-homogeneous
subcube partition is binomial.

In Section 2.8.3, we describe a construction of Perezhogin [Per05], which
gives irreducible $(n,n-1)$-homogeneous subcube partitions for all $n\geq 4$
other than $n=5$. We also show that no irreducible $(5,4)$-homogeneous subcube
partition exists, and that an irreducible $(6,4)$-homogeneous subcube
partition does exist.

In Section 2.8.4, we show how the irreducible subcube partitions constructed
in Section 2.8.3 give rise to even more irreducible subcube partitions, using
a simple inductive construction.

Finally, in Section 2.8.5 we show that an irreducible $(n,3)$-homogeneous
partition exists only for $n=4$, and in Section 2.8.6 we show that an
irreducible $(n,4)$-homogeneous partition exists only for $n=6$ (with the help
of a computer).

####  2.8.1 Elementary bounds

We start with the following general bound.

######  Lemma 2.45.

Suppose that $n\geq 4$ and $k\geq 2$. If there exists an irreducible
$(n,k)$-homogeneous subcube partition then $k+1\leq n\leq 2^{k}-3$.

###### Proof.

Let $F$ be an irreducible $(n,k)$-homogeneous subcube partition. Clearly
$n\geq k$. If $n=k$ then all subcubes in $F$ are points, and so $F$ is not
irreducible. Hence $n\geq k+1$. Since $F$ has size $2^{k}$, the upper bound
$n\leq 2^{k}-3$ follows from Theorem 2.14. ∎

The following corollary of Lemma 2.12 will be useful. The corollary itself,
and its applications below, were suggested to us by Kisielewicz [Kis23].

######  Corollary 2.46.

Let $F$ be a homogeneous subcube partition, and let $S$ be a star pattern
occurring in $F$. Among subcubes in $F$ whose star pattern is $S$, half have
even parity and half have odd parity.

###### Proof.

Since $F$ is homogeneous, all star patterns in $F$ are inclusion-minimal, and
so the corollary follows immediately from Lemma 2.12 (applied with $G=F$). ∎

We now determine when an irreducible $(n,k)$-homogeneous subcube partition
exists for $k=1$ and $k=2$.

######  Lemma 2.47.

If $F$ is an irreducible $(n,1)$-homogeneous subcube partition then $n=1$ and
$F=\\{0,1\\}$.

###### Proof.

The two subcubes in $F$ contain a single non-star position, which must be
identical. Since $F$ is tight, necessarily $n=1$, and so $F=\\{0,1\\}$. ∎

######  Lemma 2.48.

There are no irreducible $(n,2)$-homogeneous subcube partitions, for any $n$.

###### Proof.

Let $F$ be an $(n,2)$-homogeneous subcube partition. Suppose, without loss of
generality, that $00*^{n-2}\in F$. Corollary 2.46 implies that $F$ must
contain a subcube with the same star pattern and odd parity, without loss of
generality $01*^{n-2}$. Since $00*^{n-2}\cup 01*^{n-2}=0*^{n-1}$ is a subcube,
$F$ is reducible. ∎

Here is an alternative proof, suggested by the reviewer. As in the proof of
Lemma 2.45, we have $n\geq k+1=3$. On the other hand, the result of Tarsi
mentioned in the proof of Theorem 2.14 implies that $n\leq 2^{k}-1=3$. Hence
$n=3$, and this case can be ruled out by hand (and also follows from [KZ16,
Lemma 41]).

####  2.8.2 Weight distribution

In this section we prove the following surprising property, which involves the
concept of weight vector defined in Section 2.4.

######  Lemma 2.49.

The weight vector of any $(n,k)$-homogeneous subcube partition is

$\binom{k}{0},\binom{k}{1},\dots,\binom{k}{k},0,\dots,0.$

###### Proof.

Let $F$ be an $(n,k)$-homogeneous subcube partition, and let $w$ be its weight
vector. Considering the number of points of weight $\ell$ which are covered,
for each $\ell\in\\{0,\ldots,k\\}$ we have

$\sum_{r=0}^{\ell}\binom{n-k}{\ell-r}w_{r}=\binom{n}{\ell}.$

This is a triangular system of equations, and so it has a unique solution. In
other words, all $(n,k)$-homogeneous subcube partitions (if any) have the same
weight vector.

The argument above applies even if we don’t assume that $F$ is tight.
Therefore all $(n,k)$-homogeneous subcube partitions have the same weight
vector as the subcube partition $\\{x*^{n-k}:x\in\\{0,1\\}^{k}\\}$, whose
weight vector is the one in the statement of the lemma. ∎

####  2.8.3 Special perfect matchings

Perezhogin [Per05] defines a _special perfect matching_ to be a perfect
matching in the hypercube graph which is irreducible (in our terminology). If
the hypercube has dimension $n$, then this is the same as an irreducible
$(n,n-1)$-homogeneous subcube partition. He constructs a special perfect
matching for all $n\geq 4$ other than $n=5$, and shows that no special perfect
matching exists when $n=5$. In this section, we give an exposition of his
work.

We start with the construction.

######  Theorem 2.50.

For every $n\geq 4$ other than $n=5$ there exists an irreducible
$(n,n-1)$-homogeneous subcube partition.

###### Proof.

Using Lemma 2.37, it suffices to construct irreducible $(n,n-1)$-homogeneous
subcube partitions of lengths $n\in\\{4,7\\}$ containing $0^{n-1}*$ and
satisfying the complementation property in the lemma.

For $n=4$, we can take

$0*10,01*1,000*,1*01,10*0,111*,*100,*011.$

For $n=7$, we can take the subcube partition obtained by applying Lemma 2.18
with $F_{0}$ being the subcube partition constructed in Theorem 2.38 for
$n=6$, and with $F_{1}$ being obtained from $F_{0}$ by flipping the first two
coordinates. ∎

The following result shows that Theorem 2.50 cannot be extended to $n=5$.

######  Lemma 2.51.

There is no irreducible $(5,4)$-homogeneous subcube partition.

###### Proof.

Suppose that $F$ is an irreducible $(5,4)$-homogeneous subcube partition.
Every subcube in $F$ contains a single $*$. For $i\in\\{1,\dots,5\\}$, let
$F_{i}\subset F$ consist of those subcubes $s\in F$ with $s_{i}=*$. According
to Lemma 2.12, $|F_{i}|$ is even. If $|F_{i}|=0$ then the union of all
subcubes $s\in F$ with $s_{i}=0$ is the subcube $*^{i-1}0*^{5-i}$,
contradicting irreducibility, and so $|F_{i}|>0$.

The proof of Lemma 2.39 implies that for each $i\in\\{1,\dots,5\\}$, either
$|F_{i}|=2$ or $|F_{i}|=4$. Moreover, if $|F_{i}|=4$ then each coordinate in
$F_{i}$ is _balanced_ ($0$ appears the same number of times as $1$), whereas
if $|F_{i}|=2$ then exactly one coordinate is unbalanced. In the entire
formula, each coordinate is balanced, since the union of subcubes with
$s_{i}=0$ is the same as the union of subcubes with $s_{i}=1$, and each
subcube contains exactly two points.

Without loss of generality, $|F_{1}|\leq\cdots\leq|F_{5}|$. Since
$|F_{1}|+\cdots+|F_{5}|=16$, it follows that $|F_{1}|=|F_{2}|=2$ and
$|F_{3}|=|F_{4}|=|F_{5}|=4$. Recall that each of $F_{1}$ and $F_{2}$ contains
exactly one unbalanced coordinates. Since all coordinates in
$F_{3},F_{4},F_{5},F$ are balanced, $F_{1}$ and $F_{2}$ have the same
unbalanced coordinate. In particular, the second coordinate in $F_{1}$ and the
first coordinate in $F_{2}$ are balanced.

Let $F_{1}=\\{*0x_{0},*1x_{1}\\}$ and $F_{2}=\\{0*y_{0},1*y_{1}\\}$. For
$\alpha,\beta\in\\{0,1\\}$, we have $\\{s:\alpha\beta s\in F_{1}\cup
F_{2}\\}=\\{x_{\alpha},y_{\beta}\\}$. The set $\\{s:\alpha\beta s\in F_{3}\cup
F_{4}\cup F_{5}\\}$ consists of three edges, each covering a point of even
parity and a point of odd parity. Therefore $x_{\alpha}$ and $y_{\beta}$ have
opposite parity.

Suppose that $x_{\alpha}$ and $y_{\beta}$ differ in a single bit, say
$x_{\alpha}=000$ and $y_{\beta}=001$. The set $\\{s:\alpha\beta s\in F_{3}\cup
F_{4}\cup F_{5}\\}$ must be a matching of the remaining points. There are only
four possibilities:

$\displaystyle 01*,10*,11*$ $\displaystyle 01*,1*0,1*1$
$\displaystyle*10,*01,*11$ $\displaystyle*10,0*1,1*1$

In each of them, $F$ is reducible. Therefore $y_{\beta}$ must be the negation
of $x_{\alpha}$. However, this implies that $x_{0}=x_{1}$, contradicting
irreducibility. ∎

In contrast, there does exist an irreducible $(6,4)$-homogeneous subcube
partition.

######  Lemma 2.52.

There exists an irreducible $(6,4)$-homogeneous subcube partition.

###### Proof.

Here is such a subcube partition:

$\displaystyle 0000**,001**1,01*01*,01**00,0*01*1,0**110,*010*0,*0*100,$
$\displaystyle 1101**,111**0,10*11*,10**01,1*00*0,1**011,*111*1,*1*001.\qed$

Computer search reveals that up to permutation and flipping of coordinates,
the irreducible $(6,4)$-homogeneous subcube partition is unique.

####  2.8.4 More infinite families

In this section we show how any irreducible homogeneous subcube partition
gives rise to an infinite family.

######  Lemma 2.53.

Let $k\geq 2$. If there exists an irreducible $(n,k)$-homogeneous subcube
partition then there exists an irreducible $(3n,2k)$-homogeneous subcube
partition.

###### Proof.

Let $F$ be an irreducible $(n,k)$-homogeneous subcube partition. We start by
observing that for each coordinate $i$, there must be some subcube $s\in F$
with $s_{i}=*$. Otherwise, the union of the subcubes $s\in F$ with $s_{i}=0$
will be $*^{i-1}0*^{n-i}$, which contradicts irreducibility.

Repeat the following operation $n$ times to $F$: apply Lemma 2.42, and rotate
the result twice to the right (equivalently, replace $t*\in F$ with $***t$ and
$tb\in F$ with $b*0t,*b1t$, where $b\neq*$). The observation in the preceding
paragraph ensures that the resulting subcube partition $G$ is tight and
irreducible. By construction, $G$ has length $n+2n=3n$ and codimension
$k+k=2k$. ∎

Applying this to the results of Section 2.8.3, we obtain the following
infinite families.

######  Corollary 2.54.

For every $t\geq 0$ and every $n\geq 4$ other than $n=5$ there exists an
irreducible $(3^{t}\cdot n,2^{t}\cdot(n-1))$-homogeneous subcube partition.

For every $t\geq 0$ there exists an irreducible $(3^{t}\cdot 6,2^{t}\cdot
4)$-homogeneous subcube partition.

####  2.8.5 Codimension 3

Theorem 2.50 shows that an irreducible $(4,3)$-homogeneous subcube partition
exists. In this section, we show that an irreducible $(n,3)$-homogeneous
subcube partition exists only for $n=4$, and that it is unique up to
permutation and flipping of coordinates.

######  Theorem 2.55.

If there exists an irreducible $(n,3)$-homogeneous subcube partition then
$n=4$. Moreover, the irreducible $(4,3)$-homogeneous subcube partition is
unique up to permutation and flipping of coordinates.

###### Proof.

Let $F$ be an irreducible $(n,3)$-homogeneous subcube partition. We start by
proving the following claims:

  1. (i)

If $s\in F$ then $\bar{s}\in F$, where $\bar{s}$ is obtained by flipping all
bits in $s$.

  2. (ii)

If $s\in F$ then $s$ and $\bar{s}$ are the only subcubes in $F$ of the star
pattern $P(s)$.

  3. (iii)

Every two subcubes in $F$ have at least two non-star coordinates in common.

Suppose that $s\in F$, without loss of generality $s=000*^{n-3}$. Corollary
2.46 implies that $F$ contains another subcube having the same star pattern
but with opposite parity. Since $F$ is irreducible, this cannot be one of
$100*^{n-3},010*^{n-3},001*^{n-3}$, and so $111*^{n-3}\in F$, proving Item i.
Irreducibility implies that no other subcube with the same star pattern can
belong to $F$, proving Item ii. Any other subcube in $F$ must conflict with
both $000*^{n-3}$ and $111*^{n-3}$, hence must mention at least two
coordinates among the first three, proving Item iii.

Suppose now without loss of generality that $000*^{n-3}\in F$. According to
Item i, also $111*^{n-3}\in F$. According to Item ii, these are the only two
subcubes with this star pattern. Hence $F$ must contain a subcube $s$ with a
different star pattern. According to Item iii, the subcube $s$ must mention at
least two coordinates out of $\\{1,2,3\\}$. Since $s$ must conflict with both
$000*^{n-3}$ and $111*^{n-3}$, without loss of generality $s=01*0*^{n-4}\in
F$. According to Item i, also $10*1*^{n-4}\in F$, and according to Item ii,
these are the only subcubes in $F$ with this star pattern.

According to Item iii, every other subcube $t$ in $F$ must mention two
coordinates out of $\\{1,2,3\\}$ and two coordinates out of $\\{1,2,4\\}$. If
$t$ mentions coordinates $1,2$ (and a third coordinate not in $\\{3,4\\}$)
then $t$ cannot possibly conflict with all of
$000*^{n-3},111*^{n-3},01*0*^{n-4},10*1*^{n-4}$, and so $t$ must mention
either $\\{1,3,4\\}$ or $\\{2,3,4\\}$. Since $F$ is tight, we deduce that
$n=4$.

According to Item ii, $F$ contains precisely two subcubes mentioning
$\\{1,3,4\\}$ and precisely two subcubes mentioning $\\{2,3,4\\}$. Moreover,
in each pair, one of the subcubes is the negation of the other, according to
Item i. The subcube of the form $0*ab$ must be $0*11$ in order to conflict
with $000*$ and $01*0$, and so $0*11,1*00\in F$. Similarly, the subcube of the
form $*0ab$ must be $*010$ in order to conflict with $000*$ and $10*0$, and so
$*010,*101\in F$. Since $F$ contains eight subcubes, this completes the
description of $F$, and so $F$ is unique up to permutation and flipping of
coordinates. ∎

####  2.8.6 Codimension 4

Lemma 2.52 shows that an irreducible $(6,4)$-homogeneous subcube partition
exists. Using techniques similar to the preceding section, in this section we
show that an irreducible $(n,4)$-homogeneous subcube partition exists only for
$n=6$.

######  Theorem 2.56.

If there exists an irreducible $(n,4)$-homogeneous subcube partition then
$n=6$.

Since the proof is a bit long, we break it into three parts, starting with the
following lemma.

######  Lemma 2.57.

If $F$ is an irreducible $(n,4)$-homogeneous subcube partition and $s,t\in F$
are two different subcubes, then $s,t$ have at least two non-star coordinates
in common.

###### Proof.

Let $F$ be an irreducible $(n,4)$-homogeneous subcube partition. We start with
the following observations:

  1. (i)

If $u\in F$ then $F$ contains another subcube with the same star pattern
differing in exactly three coordinates.

  2. (ii)

For every coordinate $i$, there is some $v\in F$ with $v_{i}=*$.

Let $u\in F$, say $u=0000*^{n-4}$. According to Corollary 2.46, $F$ must
contain another subcube with the same star pattern and opposite parity. Since
$F$ is irreducible, this cannot be one of $1000*^{n-4},\allowbreak
0100*^{n-4},\allowbreak 0010*^{n-4},\allowbreak 0001*^{n-4}$, implying Item i.

If all $v\in F$ satisfy $v_{i}\in\\{0,1\\}$ then the union of all subcubes
with $v_{i}=0$ is the subcube $*^{i-1}0*^{n-i}$, hence $*^{i-1}0*^{n-i}\in F$
by irreducibility; but then $F$ is not $(n,4)$-homogeneous. This proves Item
ii.

Suppose, for the sake of contradiction, that $F$ contains two subcubes $s,t$
which share fewer than two non-star coordinates. Since $s,t$ conflict, they
have exactly one non-star coordinate in common. Without loss of generality,
$s=0000*^{n-4}$ and $t=***1000*^{n-7}$. Applying Item i, $F$ must contain one
of $0111*^{n-4},\allowbreak 1011*^{n-4},\allowbreak 1101*^{n-4},\allowbreak
1110*^{n-4}$. The only one of these which conflicts with $t$ is $1110*^{n-4}$.
Applying Item i to $t$, we similarly get that $***1111*^{n-7}\in F$. Thus $F$
contains the following subcubes:

$\displaystyle 0000***\,*^{n-7}$ $\displaystyle 1110***\,*^{n-7}$
$\displaystyle***1000\,*^{n-7}$ $\displaystyle***1111\,*^{n-7}$

According to Item ii with $i=4$, the subcube partition $F$ must contain a
subcube $v$ with $v_{4}=*$. In order to conflict with the first two subcubes
above, $v$ must contain a $0$ and a $1$ in coordinates $1,2,3$. In order to
conflict with the latter two subcubes, it must contain a $0$ and a $1$ in
coordinates $5,6,7$. Without loss of generality, $v$ is the following subcube:

$\displaystyle 01**01*\,*^{n-7}$

Applying Item i to $v$, one of the following subcubes belongs to $F$:

$\displaystyle 00**10*\,*^{n-7}$ $\displaystyle 11**10*\,*^{n-7}$
$\displaystyle 10**00*\,*^{n-7}$ $\displaystyle 10**11*\,*^{n-7}$

However, the $i$’th subcube in this list fails to conflict with the $i$’th
subcube in the previous list, and we reach the desired contradiction. ∎

We use Lemma 2.57 together with the following lemma to bound $n$.

######  Lemma 2.58.

Let $F$ be an irreducible $(n,k)$-homogeneous subcube partition, where $n\geq
2$. Each coordinate is mentioned in at least six subcubes of $F$.

###### Proof.

We will show that the first coordinate is mentioned at least six times. For