A specific collection of subgraphs in $K_{70, 70}$

Question

Does there exist a collection of subgraphs $\{\Gamma_i\}_{i = 1}^{24}$ of $K_{70, 70}$, that satisfy the following two properties:

1)$\Gamma_i \cong K_{i, i} \forall 1 \leq i \leq 24$;

2)Any edge of $K_{70, 70}$ belongs to exactly one subgraph from this collection?

This question appeared because, the $K_{n, n}$ always has $n^2$ vertices, and $70^2 = \Sigma_{i = 1}^{24} i^2$. Thus the numbers of edges here match perfectly. But that is clearly not enough...

Both the initial graph and the collection of subgraphs are too large to solve this question via brute force. And I do not know any other way to approach this problem.

Any help will be appreciated.

Answer 1

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.

Answer 2

Based on the comments about finding 70 partitions of 70 into distinct parts, with part $j$ appearing $j$ times among all partitions, I came up with an alternate integer linear programming formulation and found a solution. Let $P$ be the set of all (14136) partitions of 70 into distinct parts of size at most 24. For $j \in \{1,\dots,24\}$, let $P_j \subset P$ be the subset of partitions that contain part $j$. Let binary decision variable $x_p$ indicate whether partition $p\in P$ is used. The problem is to find a feasible solution to the following constraints: \begin{align} \sum_{p\in P} x_p &= 70 \\ \sum_{p\in P_j} x_p &= j &&\text{for $j \in \{1,\dots,24\}$} \\ x_p &\in \{0,1\} && \text{for $p\in P$} \end{align}

Here's one such solution:

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

Edit: Here's an updated formulation that captures both left ($i=1$) and right ($i=2$) sides and the rule that prevents the same pair $\{j,k\}$ from appearing together on both sides: \begin{align} \sum_{p\in P} x_{i,p} &= 70 &&\text{for $i\in\{1,2\}$} \\ \sum_{p\in P_j} x_{i,p} &= j &&\text{for $i\in\{1,2\}$ and $j \in \{1,\dots,24\}$} \\ \sum_{p\in P_j \cap P_k} x_{i,p} &\le j\ y_{i,j,k} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \\ y_{1,j,k} + y_{2,j,k} &\le 1 &&\text{for $1 \le j<k \le 24$} \\ x_{i,p} &\in [0,70] \cap \mathbb{Z} && \text{for $i\in\{1,2\}$ and $p\in P$} \\ y_{i,j,k} &\in \{0,1\} && \text{for $i\in\{1,2\}$ and $1 \le j<k \le 24$} \end{align}

Answer 3

I like the idea of @dvitek to use pairs of multisets of partitions as a data structure for these $K_{70,70}$ decompositions. Let me repeat the idea since it partly lives in comments.

A $K_{70,70}$ decomposition is equivalent to a particular pair $\{\mathcal{A},\mathcal{B}\}$ where each of $\mathcal{A,B}$ is a multiset of $70$ partitions into distinct parts of $70.$

Each particular edge belongs to a $K_{ii}$ for some $i.$ Label that edge $i.$ Assign each vertex the set consisting of the labels of its incident edges. This is a partition of $70.$ Finally, let $\mathcal{A,B}$ be the multisets of partitions corresponding to the two vertex classes. The following properties are satisfied:

• Among the $70$ partitions in $\mathcal{A},$ an integer $i \leq 24$ appears $i$ times and similarly for $\mathcal{B}.$

• Two partitions $\alpha,\beta$ one each from $\mathcal{A,B}$ can share at most one member. Equivalently, there is a partial edge coloring of $K_n$ using Amber and Blue so that two integers appear together in a partition $\alpha \in \mathcal{A}$ only if the corresponding edge of $K_n$ is Amber.

The converse is also true. Given such a pair of multisets of partitions, a $K_{70,70}$ decomposition is determined.

Given the second requirement, it seems that (most of) the partitions would use relatively few parts and occur to high multiplicity.

For example, perhaps $\mathcal{A}$ would use $24+23+13+10$ $10$ times and $24+17+15+14$ $14$ times ( or $a$ and $b$ times along with $24+23+14+9$ $c$ times for $a,b,c$ to be determined later subject to $a+b+c=24, a+c \leq 23, b+c \leq 9,a \leq 10, b \leq 14,c \leq 9.$) Such a start would limit the possible set of partitions using $24$ used in $\mathcal{B}$ and having chosen those, with or without their multiplicities, there might be enough restrictions to find or rule out a completion.

Alternately, there might be few enough partitions of $46$ into distinct parts (perhaps larger than $7$) to arrive at an impossibility proof.

Answer 4

You can use integer linear programming instead of brute force. Let decision variables $x_{i,c}$ and $y_{j,c}$ indicate whether left node $i$ and right node $j$ appear in $\Gamma_c$, respectively, and let decision variable $z_{i,j,c}$ indicate whether edge $(i,j)$ appears in $\Gamma_c$. Then the problem is to find a feasible solution to the following linear constraints: \begin{align} \sum_{i=1}^{70} x_{i,c} &= c &&\text{for $c\in\{1,\dots,24\}$} \\ \sum_{j=1}^{70} y_{j,c} &= c &&\text{for $c\in\{1,\dots,24\}$} \\ \sum_{j=1}^{70} z_{i,j,c} &= c\ x_{i,c} &&\text{for $i\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$} \\ \sum_{i=1}^{70} z_{i,j,c} &= c\ y_{j,c} &&\text{for $j\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$} \\ \sum_{c=1}^{24} z_{i,j,c} &= 1 &&\text{for $i,j\in\{1,\dots,70\}$} \\ z_{i,j,c} &\le x_{i,c} &&\text{for $i,j\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$}\\ z_{i,j,c} &\le y_{j,c} &&\text{for $i,j\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$}\\ z_{i,j,c} &\ge x_{i,c} + y_{j,c} - 1 &&\text{for $i,j\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$}\\ x_{i,c} &\in \{0,1\} &&\text{for $i\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$}\\ y_{j,c} &\in \{0,1\} &&\text{for $j\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$} \\ z_{i,j,c} &\in \{0,1\} &&\text{for $i,j\in\{1,\dots,70\}$, $c\in\{1,\dots,24\}$} \end{align}