On the Existence of Partition of the Hypercube Graph Into 3 Initial Segments
Ethan Soloway, Megan Triplett, Wenshi Zhao · 2025
Read On the Existence of Partition of the Hypercube Graph Into 3 Initial Segments by Ethan Soloway, Megan Triplett, Wenshi Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05827.txt.
Introduction
Splitting a hypercube graph into three initial segments is studied by Ethan Soloway, Megan Triplett, and Wenshi Zhao in a 2025 paper. An initial segment is the set of the first vertices in binary order. A pair of lengths is called fit if two moved copies of segments of those lengths always join to form the segment of their summed length, whenever the cube is large enough.
The authors give a new test for fit pairs based on a point-counting function that is easy to compute. With it, they generate the full set of unfit pairs. They also give a closed count of how many unfit pairs exist. The result ties a clean counting formula to a partition problem that looks simple but resists direct attack.
Catalog record
| CREATOR | Ethan Soloway, Megan Triplett, Wenshi Zhao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05827
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Existence of Partition of the Hypercube Graph Into 3 Initial Segments Thanks: This paper was supported in part by NSF DMS grant No. 2349684. The work for this paper was conducted during 2024 Auburn University Summer REU Ethan Soloway, Megan Triplett, Wenshi Zhao Abstract . Let Q n = { 0 , 1 } n Q_{n}=\{0,1\}^{n} be a hypercube graph. The initial segment I k ⊆ Q n I_{k}\subseteq Q_{n} is the subset consisting of the first k k vertices of Q n Q_{n} in the binary order. A pair of integers ( a , b ) ∈ ℤ > 0 2 (a,b)\in\mathbb{Z}_{>0}^{2} is said to be fit if, whenever 2 n ≥ a + b 2^{n}\geq a+b , there exists g 1 , g 2 ∈ Aut ( Q n ) g_{1},g_{2}\in\text{Aut}(Q_{n}) such that g 1 ( I a ) ∪ g 2 ( I b ) = I a + b g_{1}(I_{a})\cup g_{2}(I_{b})=I_{a+b} , and ( a , b ) (a,b) is unfit otherwise. For a + b + c = 2 n a+b+c=2^{n} , there is a partition of Q n Q_{n} into 3 3 initial segments of length a , b a,b , and c c if and only if ( a , b ) (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 ) (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 ) (a,b) , where 0 < a , b ≤ 2 n 0<a,b\leq 2^{n} , is 4 n − ( 4 1 ) 3 n + ( 4 2 ) 2 n − ( 4 1 ) 4^{n}-\binom{4}{1}3^{n}+\binom{4}{2}2^{n}-\binom{4}{1} , which is also the number of surjection of an n n -element set to a 4 4 -element set. 1. Introduction Definition 1.1 (Hypercube Graph) . Let Q_{n}:=\{0,1\}^{n} denote the set of binary strings of length n . We give Q_{n} the structure of a graph by saying that two strings x,y\in\{0,1\}^{n} share an edge iff they differ in exactly one digit. Definition 1.2 (Binary Order) . There is a canonical ordering on Q_{n} . Given x,y\in Q_{n} , we view them as binary representations of natural numbers and use the standard x\leq y ordering on the naturals. The initial segment of length a , denoted I_{a}\subseteq Q_{n} , is the set of x\in Q_{n} such that x<a . Note this is only well defined for a\leq 2^{n} . Example 1.3 . Consider I_{6}\subseteq Q_{3} . This is the set I_{6}=\{000,001,010,011,100,101\} as shown in Figure 1 . Figure 1. I_{6} in the hypercube Q_{3} Convention 1.1 . Let Aut(Q_{n}) be the set of graph automorphisms of Q_{n} . For S\subseteq Q_{n} and g\in G , we will let g(S) denote the image of S under the automorphism g . For S,T\subseteq Q_{n} , we will write S\cong T if their induced subgraphs are isomorphic. Definition 1.4 (Edge Boundary) . Let G be a finite simple graph and S\subseteq V be an arbitrary subset of vertices. Then \delta S=\{(u,v)\in E|u\in S,v\notin S\} , i.e. the set of edges with exactly one vertex in S . If we view S as partitioning V into (S,V\setminus S) , this can also be interpreted as the edges crossing the partition. Question 1.1 (Edge Isoperimetric Problem) . Fix some positive integer k . Which sets S\subseteq G with |S|=k minimize the quantity |\delta S|? In particular, people asked this question for the hypercube graph G=Q_{n} . The following theorem is originally proven in [ 2 ] , [ 3 ] , [ 4 ] , and [ 5 ] . Theorem 1.5 (Harper, Lindsey, Bernstein, Hart) . For S\subseteq Q_{n} non-empty, |S|=k , S minimizes the edge boundary iff S\cong I_{k} . Since the edge isoperimetric problem can also be viewed as minimizing the edges crossing a partition of Q_{n} into 2 sets, it is natural to consider partioning Q_{n} into 3 , or in general k sets. Definition 1.6 (Partition Boundary) . Let A=\{A_{i}\}_{i=1}^{k} be a partition of Q_{n} into k sets. Then \delta A:=\{(u,v)\in E(Q_{n})|u\in A_{i},v\in A_{j},i\neq j\} . Previous results have concerned partioning Q_{n} into k approximately equal sets, i.e. differing in cardinality by at most one (cite Bezrukov). However, in this paper we consider 3-partioning the hypercube into sets of arbitrary size. The following result, which appears on [ 1 ] p.7, gives us a convenient language. Proposition 1.7 . Consider I_{a} as an induced subgraph and let i:I_{a}\to Q_{n} be an arbitrary embedding of the initial segment of length a into Q_{n} . Then there is some g\in Aut(Q_{n}) such that i(I_{a})=g(I_{a}) . Observation 1.8 . Let A be a 3 -partition of Q_{n} such that A_{1}\cong I_{a} , A_{2}\cong I_{b} , and A_{3}\cong I_{c} , for some positive integers a+b+c=2^{n} . Then |\delta A|=\frac{1}{2}(|\delta A_{1}|+|\delta A_{2}|+|\delta A_{3}|) is minimized over all partitions of size (a,b,c) by Theorem 1.5 . It is natural to ask when Q_{n} can be partitioned into such A_{1},A_{2},A_{3} . It is also equivalent to say that given (a,b,c) , there are A,B such that A\cong I_{a} , B\cong I_{b} , and A\cup B\cong I_{a+b} , as Q_{n}\setminus(A\cup B) must then be isomorphic to I_{c} . By Proposition 1.7 , we must have A=g_{1}(I_{a}) , B=g_{2}(I_{b}) and A\cup B=g_{3}(I_{a+b}) , for some g_{1},g_{2},g_{3}\in Aut(Q_{n}) . Thus, we have g_{1}(I_{a})\cup g_{2}(I_{b})=g_{3}(I_{a+b}) . Applying g_{3}^{-1} to both sides this is equivalent to g_{1}(I_{a})\cup g_{2}(I_{b})=I_{a+b} for some g_{1},g_{2}\in Aut(Q_{n}) . Question 1.2 (Essential Question) . Given positive integers a,b with a+b\leq 2^{n} , when does there exist g_{1},g_{2}\in Aut(Q_{n}) such that g_{1}(I_{a})\cup g_{2}(I_{b})=I_{a+b} ? Definition 1.9 (Unfit Pairs) . Given a pair of positive integers (a,b) with a,b\leq 2^{n} , we say that (a,b) is fit if it satisfies the condition in Question 1.2 . Otherwise, (a,b) is called unfit . Observation 1.10 . Note that if (a,b) is a fit pair with a+b+c=2^{n} , then (b,a) , (a,c) , (c,a) , (b,c) and (c,b) are also fit pairs. Therefore, our set of fit pairs displays a 6-fold symmetry. 2. Basic Tools Definition 2.1 (Exclusive-Or) . Let x\in Q_{n} . For y\in Q_{n} , let x\oplus y denote the exclusive-or operation with inputs x and y . Equivalently, if x and y are thought of as elements of (\mathbb{Z}/2)^{n} , this is just component-wise addition. Fixing some x\in Q_{n} , the map y\mapsto x\oplus y is an automorphism of Q_{n} . Definition 2.2 (Permutation) . Let x\in Q_{n} and \sigma be a permutation of the numbers \{0,1,...n-1\} . If the binary representation for x is x_{0}x_{1}...x_{n-1} , then define \sigma(x)=x_{\sigma(0)}x_{\sigma(1)}...x_{\sigma(n-1)} . For fixed \sigma , the map y\mapsto\sigma(y) is again an automorphism of Q_{n} . Theorem 2.3 (Automorphism Decomposition) . Let g\in Aut(Q_{n}) . Then, there is a unique permutation \sigma and unique x\in Q_{n} such that g(y)=x\oplus\sigma(y) for all y\in Q_{n} . Proof. This is a translation of known results about the structure