7
$\begingroup$

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)$:

drawing of the graph

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.

$\endgroup$
6
$\begingroup$

Here is one such decomposition, found by simulated annealing:

enter image description here

enter image description here

enter image description here

enter image description here


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];
$\endgroup$

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.