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

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).

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