Chromatic number of the pancake graph
$begingroup$
EDIT: This question is superseded by Chromatic number of the pancake graph 2
The pancake graphs are described on https://en.wikipedia.org/wiki/Pancake_graph.
The WIKI page gives a rather complicated upper bound for $chi(P_n)$, that does not even a do very good job: it roughly says that $chi(P_n)$ is at most $n$ minus a small constant.
However for every positive integer $n$ following statement seems to be true:
Theorem: writing $n=3q+r$ with $0leq r<3$, we have $chi(P_n)leq 2q+r$ (so roughly $chi(P_n)leqfrac23 n$).
The proof is very short and based on one simple observation:
Claim: the subgraph of $P_n$ induced by all permutations/vertices whose first element is $1$, $2$, or $3$ (or any other set of three different elements from $[n]$) is a disjoint union of even cycles (in fact all cycles have lengths that are a small multiple of $6$).
Proof of claim:
Let $H$ be the induced subgraph, $v$ a vertex of $H$.
Then there are exactly two possible flips that result in another vertex of $H$ (e.g. $1cdots3cdots2cdots$ can only be flipped to $3cdots1cdots2cdots$ or to $2cdots3cdots1cdots$). This shows that $H$ is $2$-regular, so a disjoint union of cycles.
After exactly $6$ flips the three chosen elements are in the same order again. This might not close the cycle since the in-between elements may have changed position, but it certainly guarantees that the length of each cycle is a multiple of $6$.
Proof of theorem:
partition the vertices of $P_n$ in $V_0,ldots,V_q$, where $V_i$ contains all permutations whose first element is $3i+1$, $3i+2$, or $3i+3$.
Each induced subgraph $G[V_i]$ is $2$-colorable (by the claim) when $i<q$, and $G[V_q]$ is $r$-colorable (if $r=0$, $G[V_q]$ is empty, if $r=1$, $G[V_q]$ has only isolated vertices, if $r=2$, $G[V_q]$ consists of disjoint copies of $K_2$).
Using disjoint color sets for each of the subgraphs gives the desired upper bound.
Please verify this proof, or tell me what is wrong.
Even if it is correct, it is probably not allowed to modify the WIKI myself as long as there is no "official" publication, is it?
graph-theory coloring
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
$endgroup$
add a comment |
$begingroup$
EDIT: This question is superseded by Chromatic number of the pancake graph 2
The pancake graphs are described on https://en.wikipedia.org/wiki/Pancake_graph.
The WIKI page gives a rather complicated upper bound for $chi(P_n)$, that does not even a do very good job: it roughly says that $chi(P_n)$ is at most $n$ minus a small constant.
However for every positive integer $n$ following statement seems to be true:
Theorem: writing $n=3q+r$ with $0leq r<3$, we have $chi(P_n)leq 2q+r$ (so roughly $chi(P_n)leqfrac23 n$).
The proof is very short and based on one simple observation:
Claim: the subgraph of $P_n$ induced by all permutations/vertices whose first element is $1$, $2$, or $3$ (or any other set of three different elements from $[n]$) is a disjoint union of even cycles (in fact all cycles have lengths that are a small multiple of $6$).
Proof of claim:
Let $H$ be the induced subgraph, $v$ a vertex of $H$.
Then there are exactly two possible flips that result in another vertex of $H$ (e.g. $1cdots3cdots2cdots$ can only be flipped to $3cdots1cdots2cdots$ or to $2cdots3cdots1cdots$). This shows that $H$ is $2$-regular, so a disjoint union of cycles.
After exactly $6$ flips the three chosen elements are in the same order again. This might not close the cycle since the in-between elements may have changed position, but it certainly guarantees that the length of each cycle is a multiple of $6$.
Proof of theorem:
partition the vertices of $P_n$ in $V_0,ldots,V_q$, where $V_i$ contains all permutations whose first element is $3i+1$, $3i+2$, or $3i+3$.
Each induced subgraph $G[V_i]$ is $2$-colorable (by the claim) when $i<q$, and $G[V_q]$ is $r$-colorable (if $r=0$, $G[V_q]$ is empty, if $r=1$, $G[V_q]$ has only isolated vertices, if $r=2$, $G[V_q]$ consists of disjoint copies of $K_2$).
Using disjoint color sets for each of the subgraphs gives the desired upper bound.
Please verify this proof, or tell me what is wrong.
Even if it is correct, it is probably not allowed to modify the WIKI myself as long as there is no "official" publication, is it?
graph-theory coloring
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
$endgroup$
1
$begingroup$
You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.)
$endgroup$
– Misha Lavrov
Dec 30 '18 at 21:46
$begingroup$
@Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now.
$endgroup$
– Leen Droogendijk
Dec 31 '18 at 7:21
add a comment |
$begingroup$
EDIT: This question is superseded by Chromatic number of the pancake graph 2
The pancake graphs are described on https://en.wikipedia.org/wiki/Pancake_graph.
The WIKI page gives a rather complicated upper bound for $chi(P_n)$, that does not even a do very good job: it roughly says that $chi(P_n)$ is at most $n$ minus a small constant.
However for every positive integer $n$ following statement seems to be true:
Theorem: writing $n=3q+r$ with $0leq r<3$, we have $chi(P_n)leq 2q+r$ (so roughly $chi(P_n)leqfrac23 n$).
The proof is very short and based on one simple observation:
Claim: the subgraph of $P_n$ induced by all permutations/vertices whose first element is $1$, $2$, or $3$ (or any other set of three different elements from $[n]$) is a disjoint union of even cycles (in fact all cycles have lengths that are a small multiple of $6$).
Proof of claim:
Let $H$ be the induced subgraph, $v$ a vertex of $H$.
Then there are exactly two possible flips that result in another vertex of $H$ (e.g. $1cdots3cdots2cdots$ can only be flipped to $3cdots1cdots2cdots$ or to $2cdots3cdots1cdots$). This shows that $H$ is $2$-regular, so a disjoint union of cycles.
After exactly $6$ flips the three chosen elements are in the same order again. This might not close the cycle since the in-between elements may have changed position, but it certainly guarantees that the length of each cycle is a multiple of $6$.
Proof of theorem:
partition the vertices of $P_n$ in $V_0,ldots,V_q$, where $V_i$ contains all permutations whose first element is $3i+1$, $3i+2$, or $3i+3$.
Each induced subgraph $G[V_i]$ is $2$-colorable (by the claim) when $i<q$, and $G[V_q]$ is $r$-colorable (if $r=0$, $G[V_q]$ is empty, if $r=1$, $G[V_q]$ has only isolated vertices, if $r=2$, $G[V_q]$ consists of disjoint copies of $K_2$).
Using disjoint color sets for each of the subgraphs gives the desired upper bound.
Please verify this proof, or tell me what is wrong.
Even if it is correct, it is probably not allowed to modify the WIKI myself as long as there is no "official" publication, is it?
graph-theory coloring
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
$endgroup$
EDIT: This question is superseded by Chromatic number of the pancake graph 2
The pancake graphs are described on https://en.wikipedia.org/wiki/Pancake_graph.
The WIKI page gives a rather complicated upper bound for $chi(P_n)$, that does not even a do very good job: it roughly says that $chi(P_n)$ is at most $n$ minus a small constant.
However for every positive integer $n$ following statement seems to be true:
Theorem: writing $n=3q+r$ with $0leq r<3$, we have $chi(P_n)leq 2q+r$ (so roughly $chi(P_n)leqfrac23 n$).
The proof is very short and based on one simple observation:
Claim: the subgraph of $P_n$ induced by all permutations/vertices whose first element is $1$, $2$, or $3$ (or any other set of three different elements from $[n]$) is a disjoint union of even cycles (in fact all cycles have lengths that are a small multiple of $6$).
Proof of claim:
Let $H$ be the induced subgraph, $v$ a vertex of $H$.
Then there are exactly two possible flips that result in another vertex of $H$ (e.g. $1cdots3cdots2cdots$ can only be flipped to $3cdots1cdots2cdots$ or to $2cdots3cdots1cdots$). This shows that $H$ is $2$-regular, so a disjoint union of cycles.
After exactly $6$ flips the three chosen elements are in the same order again. This might not close the cycle since the in-between elements may have changed position, but it certainly guarantees that the length of each cycle is a multiple of $6$.
Proof of theorem:
partition the vertices of $P_n$ in $V_0,ldots,V_q$, where $V_i$ contains all permutations whose first element is $3i+1$, $3i+2$, or $3i+3$.
Each induced subgraph $G[V_i]$ is $2$-colorable (by the claim) when $i<q$, and $G[V_q]$ is $r$-colorable (if $r=0$, $G[V_q]$ is empty, if $r=1$, $G[V_q]$ has only isolated vertices, if $r=2$, $G[V_q]$ consists of disjoint copies of $K_2$).
Using disjoint color sets for each of the subgraphs gives the desired upper bound.
Please verify this proof, or tell me what is wrong.
Even if it is correct, it is probably not allowed to modify the WIKI myself as long as there is no "official" publication, is it?
graph-theory coloring
graph-theory coloring
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
edited Dec 31 '18 at 7:20
Leen Droogendijk
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
asked Dec 30 '18 at 9:51
Leen DroogendijkLeen Droogendijk
6,1751716
6,1751716
1
$begingroup$
You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.)
$endgroup$
– Misha Lavrov
Dec 30 '18 at 21:46
$begingroup$
@Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now.
$endgroup$
– Leen Droogendijk
Dec 31 '18 at 7:21
add a comment |
1
$begingroup$
You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.)
$endgroup$
– Misha Lavrov
Dec 30 '18 at 21:46
$begingroup$
@Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now.
$endgroup$
– Leen Droogendijk
Dec 31 '18 at 7:21
1
1
$begingroup$
You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.)
$endgroup$
– Misha Lavrov
Dec 30 '18 at 21:46
$begingroup$
You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.)
$endgroup$
– Misha Lavrov
Dec 30 '18 at 21:46
$begingroup$
@Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now.
$endgroup$
– Leen Droogendijk
Dec 31 '18 at 7:21
$begingroup$
@Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now.
$endgroup$
– Leen Droogendijk
Dec 31 '18 at 7:21
add a comment |
0
active
oldest
votes
Your Answer
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%2f3056658%2fchromatic-number-of-the-pancake-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3056658%2fchromatic-number-of-the-pancake-graph%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
1
$begingroup$
You probably no longer want an answer here since you have asked the follow-up question math.stackexchange.com/questions/3057032 but for completeness: yes, this argument is correct. (It is not publishable on Wikipedia in its current form, but it may be publishable in DMGT as a follow-up to Konstantinova's paper, since they published that one which proves much weaker bounds. I would take some time to see if you can prove stronger results first.)
$endgroup$
– Misha Lavrov
Dec 30 '18 at 21:46
$begingroup$
@Misha Lavrov: Thanks, I have put a note at the top of the question to tell that it is obsolete now.
$endgroup$
– Leen Droogendijk
Dec 31 '18 at 7:21