Monochromatic triangle - graph coloring
$begingroup$
I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a problem of proving the same for a smaller graph of $m_{c-1} < n$ vertices and $c-1$ colors using the Pigeonhole principle. $n$ should be a function of $c$.
This is similar to how the problem of proving that in a graph with 17 vertices where the edges are colored with 3 colors we could find a triangle can be simplified to proving that in a complete graph with 6 vertices and 2 colors there is a monochromatic triangle. Appreciate any help you could provide!
graph-theory pigeonhole-principle coloring ramsey-theory
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
$endgroup$
add a comment |
$begingroup$
I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a problem of proving the same for a smaller graph of $m_{c-1} < n$ vertices and $c-1$ colors using the Pigeonhole principle. $n$ should be a function of $c$.
This is similar to how the problem of proving that in a graph with 17 vertices where the edges are colored with 3 colors we could find a triangle can be simplified to proving that in a complete graph with 6 vertices and 2 colors there is a monochromatic triangle. Appreciate any help you could provide!
graph-theory pigeonhole-principle coloring ramsey-theory
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
$endgroup$
$begingroup$
Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers.
$endgroup$
– Zachary Hunter
Jan 6 at 19:22
$begingroup$
my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered.
$endgroup$
– Roddy MacPhee
Mar 7 at 19:45
add a comment |
$begingroup$
I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a problem of proving the same for a smaller graph of $m_{c-1} < n$ vertices and $c-1$ colors using the Pigeonhole principle. $n$ should be a function of $c$.
This is similar to how the problem of proving that in a graph with 17 vertices where the edges are colored with 3 colors we could find a triangle can be simplified to proving that in a complete graph with 6 vertices and 2 colors there is a monochromatic triangle. Appreciate any help you could provide!
graph-theory pigeonhole-principle coloring ramsey-theory
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
$endgroup$
I'm trying to find the smallest $n_c$ for which the problem of proving a complete graph with $n$ vertices with edges colored with $c$ colors has a monochromatic triangle could be simplified to a problem of proving the same for a smaller graph of $m_{c-1} < n$ vertices and $c-1$ colors using the Pigeonhole principle. $n$ should be a function of $c$.
This is similar to how the problem of proving that in a graph with 17 vertices where the edges are colored with 3 colors we could find a triangle can be simplified to proving that in a complete graph with 6 vertices and 2 colors there is a monochromatic triangle. Appreciate any help you could provide!
graph-theory pigeonhole-principle coloring ramsey-theory
graph-theory pigeonhole-principle coloring ramsey-theory
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
edited Jan 6 at 19:27
Matthew Larson
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
asked Jan 6 at 19:11
Matthew LarsonMatthew Larson
366
366
$begingroup$
Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers.
$endgroup$
– Zachary Hunter
Jan 6 at 19:22
$begingroup$
my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered.
$endgroup$
– Roddy MacPhee
Mar 7 at 19:45
add a comment |
$begingroup$
Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers.
$endgroup$
– Zachary Hunter
Jan 6 at 19:22
$begingroup$
my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered.
$endgroup$
– Roddy MacPhee
Mar 7 at 19:45
$begingroup$
Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers.
$endgroup$
– Zachary Hunter
Jan 6 at 19:22
$begingroup$
Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers.
$endgroup$
– Zachary Hunter
Jan 6 at 19:22
$begingroup$
my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered.
$endgroup$
– Roddy MacPhee
Mar 7 at 19:45
$begingroup$
my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered.
$endgroup$
– Roddy MacPhee
Mar 7 at 19:45
add a comment |
0
active
oldest
votes
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%2f3064284%2fmonochromatic-triangle-graph-coloring%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%2f3064284%2fmonochromatic-triangle-graph-coloring%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
$begingroup$
Using such methods stops giving tight bounds quickly. This is confirmed by the partial results on various Ramsey numbers.
$endgroup$
– Zachary Hunter
Jan 6 at 19:22
$begingroup$
my answer at: math.stackexchange.com/questions/935143/… shows all $K_6$ actually have 2 monchromatic triangles in 2 colors, only 3 colorings of higher $K_n$ that force both to break, need be considered.
$endgroup$
– Roddy MacPhee
Mar 7 at 19:45