Are there $3$ disjoint copies of $2K_{3,3} cup (K_{5,5} setminus C_{10})$ in $K_{11,11}$?
$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$:
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.
graph-theory
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
$endgroup$
add a comment |
$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$:
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.
graph-theory
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
$endgroup$
add a comment |
$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$:
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.
graph-theory
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
$endgroup$
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$:
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.
graph-theory
graph-theory
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
edited Jan 13 '17 at 14:25
Ethan Bolker
42.7k549113
42.7k549113
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
asked Jan 13 '17 at 14:21
Rebecca J. StonesRebecca J. Stones
20.9k22781
20.9k22781
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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:
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];
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2096176%2fare-there-3-disjoint-copies-of-2k-3-3-cup-k-5-5-setminus-c-10-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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:
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];
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
$endgroup$
add a comment |
$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:
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];
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
$endgroup$
add a comment |
$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:
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];
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
$endgroup$
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:
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];
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
answered Dec 14 '18 at 19:18
Misha LavrovMisha Lavrov
46.1k656107
46.1k656107
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2096176%2fare-there-3-disjoint-copies-of-2k-3-3-cup-k-5-5-setminus-c-10-in%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
