A382023 Number of distinct half sets in Q_n containing only pairs of antipodal vertices with the property that they form an equitable partition with their complement and are interchangable under a group automorphism of the hypercube graph.

0, 1, 3, 19, 75, 391

Offset: 1

Author

Constantinos Kourouzides, Mar 12 2025

Keywords

• nonn
• more

Comments

Let Q(n) be the standard n-dimensional hypercube graph. Two vertices x and y in Q(n) are called "opposites" if they differ in every bit. A "pairs-only half-set" in Q(n) is a subset S of size 2^(n-1) such that for every pair of opposite vertices, S either contains both of them or contains neither. By distinct half sets, we mean that any set is being counted along with its complement only once.

We say S is "equitable" if all vertices in S have the same number of neighbors inside S, and all vertices in the complement of S have the same number of neighbors inside that complement.

Define a(n) as the number of pairs-only half-sets S that are equitable and admit an automorphism of Q(n) (a combination of bitwise XOR by a mask and a permutation of the n coordinates) mapping S onto its complement. In this context, an "n-bit mask", m, means a fixed n-bit binary string. To "bitwise XOR by a mask" means: for each vertex x (which is itself an n-bit string), we look at the bits of m. Wherever m has a 1 bit, we flip (invert) that corresponding bit in x; wherever m has a 0 bit, we leave that bit in x unchanged. Thus, an automorphism of Q(n) is any combination of: 1) Bitwise XOR by an n-bit mask (flip certain bits in every vertex), and 2) A permutation of the n coordinate positions (re-label the bits in each vertex).

A specialized C++ program enumerates all distinct pairs-only half-sets, for Q(1) up to Q(6), checks which are equitable, and then tests whether they can be mapped to their complements by such an automorphism. It also checks for isomorphism using the degree sequence (which is not sufficient for isomorphism), but since a set passes the test through the existence of an automorphism, the isomorphism follows as a by-product.

Examples

			The number of distinct, pairs-only half-sets in Q(3) with the desired properties is 3.
We label the vertices of the 3-dimensional hypercube Q(3) by these eight binary strings of length 3: 000, 001, 010, 011, 100, 101, 110, 111.
A half-set in Q(3) must contain a total of 4 vertices. We are interested in picking only opposite pairs of vertices. There are exactly three such half-sets that satisfy the following conditions: (1) each half-set and its complement form an "equitable" partition (every vertex in the set has the same number of neighbors in the set, and similarly for every vertex in the complement), (2) the induced subgraphs of the set and its complement are isomorphic, and (3) there is an automorphism of Q(3) that sends the set to its complement.
Those three half-sets are:
  A = 000, 111, 101, 010
  B = 100, 011, 101, 010
  C = 000, 111, 100, 011
They satisfy the conditions because:
In cases A, B and C, the subgraphs induced by each of the sets, forms two disjoint edges, and the complement also forms two disjoint edges. This means every vertex in the set has exactly one neighbor in the set, and the same applies to the complement, so the partition is equitable. Both subgraphs are therefore isomorphic (they are the same shape).
Each of these sets can be mapped to its complement by adding a particular binary vector of length 3 to all its elements. For instance, if we add the binary vector 001 to each vertex of set A, we obtain exactly A's complement. A similar approach works for B and C.
		

Links

• Constantinos Kourouzides, C++ program