# Is it possible to decompose $K_{12,12}$ into four edge-disjoint copies of $3(K_{4,4}-I)$?

Question: Is it possible to decompose $K_{12,12}$ into four edge-disjoint copies of $3(K_{4,4}-I)$, where $I$ denotes a $1$-factor?

Here's a drawing of $3(K_{4,4}-I)$:

The same motivation for my question Are there $3$ disjoint copies of $2K_{3,3} \cup (K_{5,5} \setminus C_{10})$ in $K_{11,11}$? but just another special case.

• The number of edges in $3(K_{4,4}-I)$ is $36$ and the number of edges in $K_{12,12}$ is $144 = 4 \times 36$.

• The graph $3(K_{4,4}-I)$ is $3$-regular, and $K_{12,12}$ is $(4 \times 3)$-regular.

I previously asked Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs? which shows that $K_{12,12}$ decomposes into $12$ edge-disjoint copies of $K_{4,4}-I$, which is a necessary condition for the decomposition in this question.

Here is one such decomposition, found by simulated annealing:

Here are the details of the graphs used:

• The second graph matches vertices $$4,9,10,11$$ to $$8,5,6,4$$, vertices $$3,5,6,7$$ to $$12,3,10,9$$, and vertices $$1,2,8,12$$ to $$2,1,7,11$$.
• The third graph matches vertices $$5,7,8,9$$ to $$9,3,1,4$$, vertices $$1,2,3,12$$ to $$12,8,5,6$$, and vertices $$4,6,10,11$$ to $$2,7,11,10$$.
• The fourth graph matches vertices $$1,2,4,8$$ to $$8,12,10,9$$, vertices $$3,5,6,9$$ to $$2,7,5,11$$, and vertices $$6,10,11,12$$ to $$3,4,6,1$$.

The actual answer may not be as interesting nearly two years later, but here is my Mathematica code for the simulated annealing, which can be more broadly useful.

(Here, each $$3K_{4,4}-I$$ is represented by a pair of permutations, one of the top and one of the bottom vertices. Each step we take is randomly switching two of the numbers in one of the 8 permutations we have. The energy value of a state is the number of edges of $$K_{12,12}$$ not covered, which we eventually bring down to $$0$$.)

edges[{perm1_, perm2_}] :=
Join[
Tuples[{perm1[[1 ;; 4]], perm2[[1 ;; 4]]}],
Tuples[{perm1[[5 ;; 8]], perm2[[5 ;; 8]]}],
Tuples[{perm1[[9 ;; 12]], perm2[[9 ;; 12]]}]]~Complement~
Table[{perm1[[i]], perm2[[i]]}, {i, 1, 12}];

value[state_] := 12^2 - Length[Union @@ (edges /@ state)];
randomPerm[] := {RandomSample[Range[12]], RandomSample[Range[12]]}
randomSwitch[state_] :=
Module[{h = RandomInteger[{1, 4}], i = RandomInteger[{1, 2}], j, k,
copy = state},
{j, k} = RandomSample[Range[12], 2];
copy[[h, i, {j, k}]] = Reverse[copy[[h, i, {j, k}]]];
Return[copy];
]

currentState =
bestState = {randomPerm[], randomPerm[], randomPerm[], randomPerm[]};
currentEnergy = bestEnergy = value[currentState];
temp = 1;
While[Exp[-1/temp] > 1/1000,
Do[
nextState = randomSwitch[currentState];
nextEnergy = value[nextState];
If[nextEnergy < bestEnergy, bestState = nextState;
bestEnergy = nextEnergy];
prob = Exp[-((nextEnergy - currentEnergy)/temp)];
If[RandomReal[] < prob, currentState = nextState;
currentEnergy = nextEnergy];
, {2000}];
If[bestEnergy == 0, Break[]];
temp *= 0.99; Print[{temp, currentEnergy}]
]
Print["Done ", bestEnergy];