On the Existence of Partition of the Hypercube Graph into 3 Initial Segments

Let $Q_n=\{0,1{\}}^n$ be a hypercube graph. The initial segment $I_k\subseteq Q_n$ is the subset consisting of the first $k$ vertices of $Q_n$ in the binary order. A pair of integers $(a,b)\in {\mathbb{Z}}_{>0}^2$ is said to be fit if, whenever $2^n\ge a+b$, there exists $g_1,g_2\in \text{Aut}(Q_n)$ such that $g_1(I_a)\cup g_2(I_b)=I_{a+b}$, and $(a,b)$ is unfit otherwise. For $a+b+c=2^n$, there is a partition of $Q_n$ into $3$ initial segments of length $a,b$, and $c$ if and only if $(a,b)$ is a fit pair. Thus, the notion of fit and unfit pairs is closely related to the graph-partition problem for hypercube graphs. This paper introduces a new criterion in determining whether $(a,b)$ is fit using an easy-to-compute point-counting function and applies this criterion to generate the set of all unfit pairs. It further shows that the number of unfit pairs $(a,b)$, where $0<a,b\le 2^n$, is $4^n-\left(\genfrac{}{}{0px}{}{4}{1}\right)3^n+\left(\genfrac{}{}{0px}{}{4}{2}\right)2^n-\left(\genfrac{}{}{0px}{}{4}{1}\right)$, which is also the number of surjection of an $n$-element set to a $4$-element set.