12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't see why the graph theoretic setup is relevant. If you had a suitable collection of 70 partitions of 70 (i.e., exactly one 1 in the 70 partitions, exactly two 2s, etc. up to 24) you could build such a decomposition. Conversely, looking at one of the sets of 70 vertices in the $K_{70,70}$ gives you such a decomposition; in fact given any two such sets of partitions you can construct a decomposition of the $K_{70,70}$. It's not clear to me whether this partition problem is amenable to a realistic amount of brute force, but it is certainly not less amenable to brute force. $\endgroup$ – dvitek Sep 7 '19 at 15:53
  • 2
    $\begingroup$ This is a discrete version of the "squaring the square" problem: en.wikipedia.org/wiki/Squaring_the_square $\endgroup$ – Brendan McKay Sep 8 '19 at 18:40
  • 1
    $\begingroup$ Maybe some of the techniques used here can be helpful: onlinelibrary.wiley.com/doi/pdf/10.1002/jcd.3180030608 $\endgroup$ – Brendan McKay Sep 8 '19 at 18:44
  • 1
    $\begingroup$ It seems I asked the same question at math.SE here. I'm interested in the question, because I want to know if there's a $70 \times 70$ Latin square that decomposes into subsquares of orders $1$ through $24$, and the existence of this graph decomposition is a prerequisite. $\endgroup$ – Rebecca J. Stones Sep 13 '19 at 2:15
  • 1
    $\begingroup$ Yanior Weg, I won't be surprised if Rob provides a solution soon (unless there is none) but at the moment there is no solution. If you "accept" an answer which doesn't solve the problem, you discourage other people from looking at the problem. So I strongly recommend that you unaccept the answer so that this great question is still marked as unsolved. $\endgroup$ – Brendan McKay Sep 13 '19 at 4:06
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ There are 14136 partitions in total, of which 3907 have no 1 or 2. More can be said about how the partitions fit together but I also don't see a plausible exhaustive search here. $\endgroup$ – Brendan McKay Sep 11 '19 at 2:04
  • $\begingroup$ So, let one of partitions start with $24+13+\dots$ --- both for some vertex $v$ in one part and for some vertex $u$ in the other. Then the edge $uv$ lies in both $\Gamma_{24}$ and $\Gamma_{13}$... (Sorry for incomprehensible form of the previous version of the comment.) $\endgroup$ – Ilya Bogdanov Sep 11 '19 at 14:29
  • 1
    $\begingroup$ I think your construction will give a bipartite multigraph, regular of degree $70.$ To be a simple graph it would be necessary that a partition on the left and a partition on the right share at most one common member. Is that possible? It would seem promising to have large overlaps on each side such as $24+18+15+13$ repeated $13$ times on the left and $24+20+16+12$ repeated $12$ times on the right. But then none of the other $11$ on the right with a $24$ could use $20,16$ or $12.$ $\endgroup$ – Aaron Meyerowitz Sep 11 '19 at 18:50
  • $\begingroup$ @AaronMeyerowitz Oops, yes, that's correct. I will edit my post accordingly. $\endgroup$ – dvitek Sep 12 '19 at 0:21
1
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ I see the 70 partitions corresponding to the vertices on one side of the $K_{70,70}$, but I don't see how to make a partition of $K_{70,70}$ out of them. $\endgroup$ – Brendan McKay Sep 12 '19 at 4:29
  • 2
    $\begingroup$ Hmm, I guess after the edits to @dvitek's answer we need two such sets of partitions, with no pair of parts appearing together on both sides? $\endgroup$ – Rob Pratt Sep 12 '19 at 4:40
  • $\begingroup$ Yes, that should do it. $\endgroup$ – Brendan McKay Sep 12 '19 at 6:15
  • $\begingroup$ @RobPratt What software are you using to do the integer linear programming? $\endgroup$ – dvitek Sep 12 '19 at 20:28
  • $\begingroup$ I am using SAS. $\endgroup$ – Rob Pratt Sep 12 '19 at 21:42
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Assign each vertex the partition corresponding to the $i$ such that some $𝐾_{𝑖𝑖}$ uses that vertex." I don't understand that or why it is needed. The 70 partitions on each side can be assigned to vertices arbitrarily. $\endgroup$ – Brendan McKay Sep 17 '19 at 2:21
  • $\begingroup$ And when this assignment is done, each vertex on that side is labelled by some partition. Likewise each vertex on the other side is labelled by some partition. Then we know which $2j$ vertices to use for the one copy of $K_{jj}.$ The result is (isomorphic to) the original graph. Perhaps it was originally presented in a nice manner that makes it clear it arises from a squared square (if it does). After extracting the partitions and arbitrarily reassigning them it is as if we acted on the graph by some $\sigma \in S_{70} \times S_{70} .$ It might be less nice, but still the same decomposition. $\endgroup$ – Aaron Meyerowitz Sep 17 '19 at 4:37
  • $\begingroup$ I understand the situation, but I still think the sentence I quoted is nearly incomprehensible and I suggest you reword it. By the way, there are 47 partitions of 46 into distinct parts from [8,...,24]. $\endgroup$ – Brendan McKay Sep 17 '19 at 5:39
  • $\begingroup$ I should have said “consisting of those I” I tried a longer description. $\endgroup$ – Aaron Meyerowitz Sep 17 '19 at 7:07
0
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ If there is a solution, it might be found quickly. If there isn't a solution, you'd better hope that the software has exceptionally good symmetry breaking to cope with the $(70!)^2$ symmetry. $\endgroup$ – Brendan McKay Sep 8 '19 at 19:20
  • $\begingroup$ Modern integer linear programming solvers do handle such symmetry automatically, but I found a solution by using a different formulation, which I'll post as a separate answer. $\endgroup$ – Rob Pratt Sep 12 '19 at 3:26

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.