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

Ethan Soloway; Megan Triplett; Wenshi Zhao

paper

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

arXiv:2501.05827

Abstract

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 Z_{> 0}^{2}$ is said to be fit if, whenever $2^{n} \geq a + b$ , there exists $g_{1}, g_{2} \in 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 \leq 2^{n}$ , is $4^{n} - (1 4) 3^{n} + (2 4) 2^{n} - (1 4)$ , which is also the number of surjection of an $n$ -element set to a $4$ -element set.