7
$\begingroup$

Question: Are there $3$ edge disjoint copies of $H:=2K_{3,3} \cup (K_{5,5} \setminus C_{10})$ in $K_{11,11}$?

Here's a drawing of $H$:

$2K_{3,3} \cup (K_{5,5} \setminus C_{10})$

I'm working on a Latin squares research problem and trying to get a construction to work. If it would work, it would give a solution to this problem. Only, I can't get it to work easily. Maybe the above doesn't exist, and my construction won't work in this case.

  • We see $H$ is regular with degree $3$, and the degrees of vertices in $K_{11,11}$ is $11$, so no clash there.
  • $H$ has $33$ edges while $K_{11,11}$ has $121$ edges, so no clash there.
$\endgroup$
4
$\begingroup$

Since I solved the other linked problem, I figured I might as well give simulated annealing a go on this one.

The answer is also yes; in fact, here, we can find $3$ disjoint copies of $2K_{3,3} \cup (K_{5,5} - P_{10})$. I added the extra edge in an attempt to make the problem a bit more constrained so that the solution would come out nicer, but I'm not sure how much of an effect it had.

The solution I found is below:

enter image description here

Here is my simulated annealing code (it might take a few tries before finding a zero-energy solution):

edges[{perm1_, perm2_}] :=
  Join[
   Tuples[{perm1[[1 ;; 3]], perm2[[1 ;; 3]]}],
   Tuples[{perm1[[4 ;; 6]], perm2[[4 ;; 6]]}],
   Complement[
    Tuples[{perm1[[7 ;; 11]], perm2[[7 ;; 11]]}],
    Table[{perm1[[i]], perm2[[i]]}, {i, 7, 11}],
    Table[{perm1[[i]], perm2[[i + 1]]}, {i, 7, 10}]]];
value[state_] := 102 - Length[Union @@ (edges /@ state)];
randomPerm[] := {RandomSample[Range[11]], RandomSample[Range[11]]}
newState[] := {{Range[11], Range[11]}, randomPerm[], randomPerm[]};
randomSwitch[state_] := 
 Module[{h = RandomInteger[{2, 3}], i = RandomInteger[{1, 2}], j, k, 
   copy = state},
  {j, k} = RandomSample[Range[11], 2];
  copy[[h, i, {j, k}]] = Reverse[copy[[h, i, {j, k}]]];
  Return[copy];
  ]

currentState = bestState = newState[];
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];
  , {3000}];
 If[bestEnergy == 0, Break[]];
 temp *= 0.99; Print[{temp, currentEnergy}]
 ]
Print["Done ", bestEnergy];
| cite | improve this answer | |
$\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.