Skip to main content
2 of 2
added extra condition
dvitek
  • 1.7k
  • 18
  • 29

This is an expanded version of my comment on the question, per Ilya Bogdanov's request.

Suppose that we have such a decomposition of $K_{70,70}$. Fix some vertex $v$ (say in the left half) and consider all the 70 edges of $v$. If $v \in V(\Gamma_{24})$, then 24 of these edges come from the $\Gamma_{24}$. In general we know that $$\{i | v \in V(\Gamma_i) \}$$ is a partition - call it $P(v_i)$ - of 70. Furthermore, this partition has no repeated parts.

So for each $v_i, 1 \le i \le 70$, we get a partition $P(v_i)$ of 70; call this collection $\mathcal{P}$. As a whole, the multiset $$\bigcup \mathcal{P} = P(v_1) \cup P(v_2) \cup \cdots \cup P(v_{70})$$ must contain exactly one 1, exactly two 2s, and so on up to exactly twenty-four 24s.

Hence, given such a decomposition we get a system of partitions as described (i.e., the appropriate number of 1s, 2s, etc. and no repeated parts). Note that this system corresponds to the left half of the vertices; we will get another system (possibly definitely different) if we look at the right half of the vertices.

EDIT, following Ilya's and Aaron's comments. In order for the graph to be a simple $K_{70,70}$, and not just a 70-regular bipartite graph, it is necessary that the left and right partitions have the following property: if $1 \le i, j \le 24$ occur in the same partition in the left system $\mathcal{L}$, then no partition in $\mathcal{R}$ contains both $i$ and $j$.


Now we show the converse: given such a system, we can construct a decomposition of the $K_{70,70}$. For ease of exposition, we will assume that we have two such systems $\mathcal{L}$ and $\mathcal{R}$; it will be clear that we can take $\mathcal{L} = \mathcal{R}$ so one such system will suffice.

We need to specify which vertices are in the $\Gamma_i$; this suffices as the $\Gamma_i$ are induced subgraphs of the $K_{70,70}$. But this is straightforward: the vertices that are in the left half of $\Gamma_i$ are the partitions in the partition system $\mathcal{L}$ that contain $i$, and similarly for the right half and $\mathcal{R}$.


The existence of such a partition system is a necessary and sufficient condition for the existence of such a decomposition of $K_{70,70}$. It is clear that this is combinatorially simpler than thinking about the subgraphs themselves; in particular there are fewer than 30000 partitions of 70 with distinct parts, and probably substantially fewer with no 1s or 2s (which at least 67 of the 70 partitions must have). It's still not possible to naively exhaust, but oh well.

dvitek
  • 1.7k
  • 18
  • 29