4

This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering:

Can the (edges of the) complete graph $K_{16}$ be partitioned into $10$ cube graphs $Q_3$?

By brute force, this can probably be done (or refuted??) in seconds, but are there really no more elegant methods?

A related question: Start with the tesseract graph $Q_4$ and remove a certain 1-factor (= a perfect matching, i.e. 8 isolated edges). Call the resulting 3-regular graph $G$. For which choices of the 1-factor is it possible to cover $K_{16}$ by $5$ copies of $G$?
Note that if we remove 8 “parallel” edges of the hypercube, $G$ is a (disconnected) $2Q_3$, and so the resulting question is more constrained than the initial question of covering $K_{16}$ by $10$ copies of $Q_3$.

FWIW: Intuitively, I would conjecture that none of those decompositions exists. In that case, a weaker question would be whether at least, $K_{16}$ may be covered by $5$ (possibly different) graphs of the type "$Q_4\backslash 8K_2$". Or might there even be a kind of parity argument to disprove that altogether, knowing that all those $G$ are bipartite?

Wolfgang
  • 13,193

1 Answers1

1

Such a decomposition exists. In particular a decomposition of 5 copies of $2Q_3$ exists.

We can label each vertex with a binary number from 0000 to 1111 (or more mathematically with elements of $C_2^4$). Note that each three linearly independent numbers $a, b, c$ correspond to a copy of $2Q_3$ by connecting $u$ and $v$ if and only if $u \oplus v \in \{a,b,c\}$.

Thus we need to partition $\{0001, \ldots, 1111\}$ into five linearly independent sets. You can easily do this by hand, but if you want to use more fancy math you might want to look into partitioning the multiplicative group $C_{15}$ of the finite field of order $F_{16}$. For example, $\{\{a^{3n}, a^{3n+1}, a^{3n+2}\} \mid n \in \{1,2,3,4,5\}\}$ where $a$ is a generator.

1001
  • 551