Csdrhrt

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];