5
$\begingroup$

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)?

The obvious necessary conditions work:

  • $K_{12,12}$ has $12^2$ edges which is divisible by $12$, the number of edges in $K_{4,4}-I$.

  • Vertices in $K_{12,12}$ have degree $12$ which is divisible by $3$, the degree of the vertices in $K_{4,4}-I$.

I haven't put too much effort into solving this thus far. It seems like it would require considerable effort to solve computationally, so I'm hoping there is a cleverer solution.

An alternative way of thinking about this problem:

Q: Does there exist a $12 \times 12$ matrix containing $12$ copies of each symbol in $\{1,2,\ldots,12\}$ such that each row and each column containing a copy of symbol $i$ contains exactly $3$ copies of $i$?

This question is a specific instance of another problem I'm thinking about.

$\endgroup$
  • $\begingroup$ It seems to me that just to get a single number placed in the matrix uses up four rows and four columns, with one diagonal missing (such diagonals can be at either angle, and "wrap around" mod 4). So I couldn't seem to get more than nine numbers in, and after that the remaining parts seemed not to be arrangable so as to place even the tenth number. $\endgroup$ – coffeemath Jul 10 '14 at 6:37
  • 1
    $\begingroup$ Maybe. But the same argument works for $K_{6,6}$ and $K_{3,3}-I$, but my computer found an example in this case: $$\begin{array}{|cccccc|} \hline 1 & 1 & 2 & 2 & 3 & 3 \\ 1 & 3 & 1 & 4 & 4 & 3 \\ 4 & 1 & 1 & 2 & 4 & 2 \\ 4 & 5 & 5 & 4 & 6 & 6 \\ 5 & 3 & 5 & 6 & 3 & 6 \\ 5 & 5 & 2 & 6 & 6 & 2 \\ \hline \end{array}.$$ $\endgroup$ – Rebecca J. Stones Jul 10 '14 at 6:43
  • $\begingroup$ Interesting example. Only three of the four subsquares are of the "missing diagonal" type. The upper left has all the 4,3,2 missed from the other squares using up the 1,5,6. Maybe a construction like that could work for the 12x12... $\endgroup$ – coffeemath Jul 10 '14 at 10:21
  • $\begingroup$ I meant the upper right above... $\endgroup$ – coffeemath Jul 10 '14 at 10:46
  • $\begingroup$ Rebecca: I think I found a 12 by 12 matrix with the properties of the alternate way to view the problem. (See answer below.) It took a while to get the lower right 4 by 4 block to work out with the rest. $\endgroup$ – coffeemath Jul 10 '14 at 23:24
3
$\begingroup$

[Edit (by Rebecca): the second version was correct, but let me tidy things up a bit.]

$$ \begin{array}{|cccccccccccc|} \hline 5&1&1&1&9&2&2&2&5&5&9&9 \\ 1&5&1&1&2&9&2&2&5&5&9&9\\ 1&1&6&1&2&2&10&2&6&6&10&10\\ 1&1&1&6&2&2&2&10&6&6&10&10\\ 11&3&3&3&7&4&4&4&11&11&7&7\\ 3&11&3&3&4&7&4&4&11&11&7&7\\ 3&3&12&3&4&4&8&4&12&12&8&8\\ 3&3&3&12&4&4&4&8&12&12&8&8\\ 5&5&6&6&9&9&10&10&5&6&9&10\\ 5&5&6&6&9&9&10&10&6&5&10&9\\ 11&11&12&12&7&7&8&8&11&12&7&8\\ 11&11&12&12&7&7&8&8&12&11&8&7\\ \hline \end{array} $$

In color:

Version with cells colored

And here's an illustration of the decomposition:

Decomposition of $K_{12,12}$ into $K_{4,4}-I$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow that's really nice!!! Thanks for that. (PS. I can't see the uploaded pictures from my location; hopefully I attached the right pics and they look decent.) $\endgroup$ – Rebecca J. Stones Jul 11 '14 at 2:36
  • $\begingroup$ @Rebecca -- Yes the colored version looks neat (from my viewing site anyway)! $\endgroup$ – coffeemath Jul 11 '14 at 3:31
  • $\begingroup$ I believe this construction generalizes to give: $K_{12k^2,12k^2}$ decomposes into $K_{4k,4k}-kI$ for all $k \geq 1$. This is the $k=1$ case. (More formally, there exists $k$ disjoint $1$-factors of $K_{4k,4k}$ such that if we delete them to form graph $G$, then $K_{12k^2,12k^2}$ decomposes into $G$ subgraphs.) Fascinating. $\endgroup$ – Rebecca J. Stones Jul 11 '14 at 6:14
2
$\begingroup$

Actually, there seems to be an easy construction that I overlooked when writing my question:

  • $K_{6,6}$ decomposes into three $K_{4,4}-I$ subgraphs (illustrated below).
  • We can combine four of these to decompose $K_{12,12}$ into $K_{4,4}-I$ subgraphs.

The non-edges happen to be at just the right spots for this to work:

Decomposition of $K_{6,6}$ into three $K_{4,4}-I$ subgraphs

Here's the matrix version:

$$ \begin{array}{|cccccc|} \hline 2 & 1 & 1 & 1 & 2 & 2 \\ 1 & 2 & 1 & 1 & 2 & 2 \\ 1 & 1 & 1 & 3 & 3 & 3 \\ 1 & 1 & 3 & 1 & 3 & 3 \\ 2 & 2 & 3 & 3 & 3 & 2 \\ 2 & 2 & 3 & 3 & 2 & 3 \\ \hline \end{array} \longrightarrow \begin{array}{|cccccc|cccccc|} \hline 2 & 1 & 1 & 1 & 2 & 2 & 8 & 7 & 7 & 7 & 8 & 8 \\ 1 & 2 & 1 & 1 & 2 & 2 & 7 & 8 & 7 & 7 & 8 & 8 \\ 1 & 1 & 1 & 3 & 3 & 3 & 7 & 7 & 7 & 9 & 9 & 9 \\ 1 & 1 & 3 & 1 & 3 & 3 & 7 & 7 & 9 & 7 & 9 & 9 \\ 2 & 2 & 3 & 3 & 3 & 2 & 8 & 8 & 9 & 9 & 9 & 8 \\ 2 & 2 & 3 & 3 & 2 & 3 & 8 & 8 & 9 & 9 & 8 & 9 \\ \hline 5 & 4 & 4 & 4 & 5 & 5 & 11 & 10 & 10 & 10 & 11 & 11 \\ 4 & 5 & 4 & 4 & 5 & 5 & 10 & 11 & 10 & 10 & 11 & 11 \\ 4 & 4 & 4 & 6 & 6 & 6 & 10 & 10 & 10 & 12 & 12 & 12 \\ 4 & 4 & 6 & 4 & 6 & 6 & 10 & 10 & 12 & 10 & 12 & 12 \\ 5 & 5 & 6 & 6 & 6 & 5 & 11 & 11 & 12 & 12 & 12 & 11 \\ 5 & 5 & 6 & 6 & 5 & 6 & 11 & 11 & 12 & 12 & 11 & 12 \\ \hline \end{array} $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.