26
$\begingroup$

The complete bipartite graph $K_{n,n}$ has $n^2$ edges. There's a curious number quirk that $$70^2=4900=1^2+2^2+\cdots+24^2.$$ This motivates the question:

Question: Does $K_{70,70}$ decompose into subgraphs isomorphic to $K_{1,1}$ through $K_{24,24}$?

I just ask out of simple curiosity since the number of edges checks out.

It's equivalent to asking for a $70 \times 70$ matrix which contains symbols $1,\ldots,24$ where symbol $i$ belongs to an $i \times i$ all-$i$ matrix.

One sanity check: If it were possible, for each vertex in one part, we could write down the values of $k$ for which it intersects the $K_{k,k}$ used to decompose $K_{70,70}$. This list would contain $1$ through $24$, with the number $i$ occurring exactly $i$ times, and no repeats in the rows. I found an example of such a list:

[1, 22, 23, 24], [2, 21, 23, 24], [2, 21, 23, 24], [3, 10, 16, 18, 23], [3, 14, 16, 17, 20], [3, 20, 23, 24], [4, 14, 15, 16, 21], [4, 15, 16, 17, 18], [4, 21, 22, 23], [4, 21, 22, 23], [5, 13, 15, 16, 21], [5, 19, 22, 24], [5, 20, 21, 24], [5, 20, 22, 23], [5, 20, 22, 23], [6, 13, 14, 16, 21], [6, 13, 14, 18, 19], [6, 17, 23, 24], [6, 19, 22, 23], [6, 19, 22, 23], [6, 20, 21, 23], [7, 12, 15, 16, 20], [7, 13, 14, 15, 21], [7, 18, 21, 24], [7, 18, 21, 24], [7, 18, 22, 23], [7, 18, 22, 23], [7, 20, 21, 22], [8, 10, 13, 17, 22], [8, 11, 12, 15, 24], [8, 11, 13, 17, 21], [8, 13, 15, 16, 18], [8, 17, 22, 23], [8, 19, 20, 23], [8, 19, 20, 23], [8, 19, 20, 23], [9, 10, 12, 15, 24], [9, 11, 12, 17, 21], [9, 12, 13, 17, 19], [9, 17, 20, 24], [9, 17, 20, 24], [9, 18, 19, 24], [9, 18, 19, 24], [9, 18, 21, 22], [9, 19, 20, 22], [10, 12, 14, 16, 18], [10, 15, 21, 24], [10, 15, 21, 24], [10, 17, 19, 24], [10, 17, 20, 23], [10, 18, 20, 22], [10, 18, 20, 22], [11, 12, 13, 15, 19], [11, 12, 14, 16, 17], [11, 12, 14, 16, 17], [11, 12, 23, 24], [11, 13, 22, 24], [11, 16, 19, 24], [11, 16, 19, 24], [11, 16, 21, 22], [12, 14, 20, 24], [12, 14, 21, 23], [13, 14, 19, 24], [13, 15, 20, 22], [13, 17, 18, 22], [14, 15, 18, 23], [14, 15, 19, 22], [14, 15, 20, 21], [16, 17, 18, 19], [16, 17, 18, 19]

This means arguments involving degrees alone cannot exclude this possibility.

In the matrix equivalence, this means that we can specify the columns the all-$i$ submatrices intersect in a non-clashing way (but it doesn't simultaneously give the rows).

$\endgroup$
3
  • $\begingroup$ Reminds me a bit of this old chestnut en.wikipedia.org/wiki/Squaring_the_square $\endgroup$ Aug 27, 2017 at 9:21
  • 2
    $\begingroup$ It's nearly a specific case of "squaring the square", but the submatrices need not be contiguous in this question. $\endgroup$ Aug 27, 2017 at 9:34
  • 2
    $\begingroup$ According to this recent question, “it is known that squares with side 1-24 can't quite pack in a side 70 square”. $\endgroup$ Sep 9, 2017 at 7:53

1 Answer 1

2
$\begingroup$

Such decomposition does exist.

It was constructed in the answer to this MO question.

Note, that the complete answer there is formed by two answers by different users: the answer by @RobPratt gives us the explicit construction of such decomposition and the answer by @dvitek provides us with the theoretical base for this construction.

$\endgroup$
2
  • 2
    $\begingroup$ Is it actually constructed yet? @RobPratt's answer only gives half of the construction. $\endgroup$ Sep 12, 2019 at 20:31
  • $\begingroup$ Thanks for pointing out the connection between the two questions. However, they haven't constructed one at MathOverflow yet. dvitek's answer gives a requirement on left and right partitions. We have one partition given by RobPratt (and also by me as a "sanity check" for this question), but not a second partition satisfying the requirement. (Brendan McKay, Ilya Bogdanov, Aaron Meyerowitz all make comments to this effect.) $\endgroup$ Sep 13, 2019 at 2:48

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.