Mixing
Colouring a sequence
$begingroup$
Define a 2 coloring of $left { left. 0,1 right }^* right.$ to be a function $chi:left { left. 0,1 right }^* right. rightarrow left { left. red,blue right } right. $
e.g. if $chi(1101)=red$, we say that 1101 is red in the coloring of $chi$.
Prove: For every 2 coloring $chi$ of $left { left. 0,1 right }^* right.$ and every (infinite) binary sequence $S in left { left. 0,1 right }^infty right.$
There is a sequence:
$$w_{0},w_{1},w_{2},...$$
of strings $w_{n} in left { left. 0,1 right }^* right.$ such that:
i) $S= w_{0}w_{1}w_{2}...$ and
ii) $w_{1},w_{2},...$ are all the same color. (The string $w_{0}$ may not be this color).
I have tried making arguments that you can split any sequence and define each 'half' as the colorings. This then fails for an infinite sequence. I am not sure how to 'prove' such a result. I'm not sure if you can split it into cases where the infinite sequence is repeating or non-repeating etc.
Thanks for any help
combinatorics coloring
asked Jan 30 at 9:29
LehmannLehmann
262
$endgroup$
add a comment |
$begingroup$
Define a 2 coloring of $left { left. 0,1 right }^* right.$ to be a function $chi:left { left. 0,1 right }^* right. rightarrow left { left. red,blue right } right. $
e.g. if $chi(1101)=red$, we say that 1101 is red in the coloring of $chi$.
Prove: For every 2 coloring $chi$ of $left { left. 0,1 right }^* right.$ and every (infinite) binary sequence $S in left { left. 0,1 right }^infty right.$
There is a sequence:
$$w_{0},w_{1},w_{2},...$$
of strings $w_{n} in left { left. 0,1 right }^* right.$ such that:
i) $S= w_{0}w_{1}w_{2}...$ and
ii) $w_{1},w_{2},...$ are all the same color. (The string $w_{0}$ may not be this color).
I have tried making arguments that you can split any sequence and define each 'half' as the colorings. This then fails for an infinite sequence. I am not sure how to 'prove' such a result. I'm not sure if you can split it into cases where the infinite sequence is repeating or non-repeating etc.
Thanks for any help
combinatorics coloring
asked Jan 30 at 9:29
LehmannLehmann
262
$endgroup$
$begingroup$
Shouldn't $w_1w_2$, $w_2w_3$, $w_1w_2w_3$, $w_3w_4$, $w_2w_3w_4$, $w_1w_2w_3w_4$, $w_4w_5$, etc. also be the same color as $w_2$, $w_2$, $w_3$, etc.?
$endgroup$
– bof
Jan 30 at 9:52
$begingroup$
Isn't this a direct consequence of Ramsey's theorem?
$endgroup$
– bof
Jan 30 at 10:01
$begingroup$
@bof: No, why? $Chi$ is any colouring. My idea will be to have an infinite graphs with vertices $u_ildots u_j$ where $S=u_0u_1ldots$ and each $u_iin{0,1}$. $u_ildots u_j$ would be connected to $u_{j+1}ldots u_k$ by a directed edge colored "c" if $Chi(u_ildots u_j)=Chi(u_{j+1}ldots u_k)=c$. Probably some kind of Ramsey-like argument could be applied on that.
$endgroup$
– Faustus
Jan 30 at 10:02
1
$begingroup$
@Faustus My idea would be to consider a graph with vertices $0,1,2,3,dots$; for $ilt j$, vertices $i$ and $j$ would be joined by an edge of color $c$ if $chi(u_{i+1}u_{i+2}dots u_j)=c$. By Ramsey's theorem there is an infinite sequence $i_0lt i_1lt i_2ltcdots$ such that all edges joining any two of them are the same color. Then let $w_0=u_0dots u_{i_0}$, $w_1=u_{i_0+1}dots u_{i_1}$, etc.
$endgroup$
– bof
Jan 30 at 12:13
add a comment |
$begingroup$
Define a 2 coloring of $left { left. 0,1 right }^* right.$ to be a function $chi:left { left. 0,1 right }^* right. rightarrow left { left. red,blue right } right. $
e.g. if $chi(1101)=red$, we say that 1101 is red in the coloring of $chi$.
Prove: For every 2 coloring $chi$ of $left { left. 0,1 right }^* right.$ and every (infinite) binary sequence $S in left { left. 0,1 right }^infty right.$
There is a sequence:
$$w_{0},w_{1},w_{2},...$$
of strings $w_{n} in left { left. 0,1 right }^* right.$ such that:
i) $S= w_{0}w_{1}w_{2}...$ and
ii) $w_{1},w_{2},...$ are all the same color. (The string $w_{0}$ may not be this color).
I have tried making arguments that you can split any sequence and define each 'half' as the colorings. This then fails for an infinite sequence. I am not sure how to 'prove' such a result. I'm not sure if you can split it into cases where the infinite sequence is repeating or non-repeating etc.
Thanks for any help
combinatorics coloring
asked Jan 30 at 9:29
LehmannLehmann
262
$endgroup$
Define a 2 coloring of $left { left. 0,1 right }^* right.$ to be a function $chi:left { left. 0,1 right }^* right. rightarrow left { left. red,blue right } right. $
e.g. if $chi(1101)=red$, we say that 1101 is red in the coloring of $chi$.
Prove: For every 2 coloring $chi$ of $left { left. 0,1 right }^* right.$ and every (infinite) binary sequence $S in left { left. 0,1 right }^infty right.$
There is a sequence:
$$w_{0},w_{1},w_{2},...$$
of strings $w_{n} in left { left. 0,1 right }^* right.$ such that:
i) $S= w_{0}w_{1}w_{2}...$ and
ii) $w_{1},w_{2},...$ are all the same color. (The string $w_{0}$ may not be this color).
I have tried making arguments that you can split any sequence and define each 'half' as the colorings. This then fails for an infinite sequence. I am not sure how to 'prove' such a result. I'm not sure if you can split it into cases where the infinite sequence is repeating or non-repeating etc.
Thanks for any help
combinatorics coloring
combinatorics coloring
asked Jan 30 at 9:29
LehmannLehmann
262
asked Jan 30 at 9:29
LehmannLehmann
262
edited Jan 30 at 9:48
Lehmann
asked Jan 30 at 9:29
LehmannLehmann
262
asked Jan 30 at 9:29
LehmannLehmann
262
asked Jan 30 at 9:29
LehmannLehmann
262
262
$begingroup$
Shouldn't $w_1w_2$, $w_2w_3$, $w_1w_2w_3$, $w_3w_4$, $w_2w_3w_4$, $w_1w_2w_3w_4$, $w_4w_5$, etc. also be the same color as $w_2$, $w_2$, $w_3$, etc.?
$endgroup$
– bof
Jan 30 at 9:52
$begingroup$
Isn't this a direct consequence of Ramsey's theorem?
$endgroup$
– bof
Jan 30 at 10:01
$begingroup$
@bof: No, why? $Chi$ is any colouring. My idea will be to have an infinite graphs with vertices $u_ildots u_j$ where $S=u_0u_1ldots$ and each $u_iin{0,1}$. $u_ildots u_j$ would be connected to $u_{j+1}ldots u_k$ by a directed edge colored "c" if $Chi(u_ildots u_j)=Chi(u_{j+1}ldots u_k)=c$. Probably some kind of Ramsey-like argument could be applied on that.
$endgroup$
– Faustus
Jan 30 at 10:02
1
$begingroup$
@Faustus My idea would be to consider a graph with vertices $0,1,2,3,dots$; for $ilt j$, vertices $i$ and $j$ would be joined by an edge of color $c$ if $chi(u_{i+1}u_{i+2}dots u_j)=c$. By Ramsey's theorem there is an infinite sequence $i_0lt i_1lt i_2ltcdots$ such that all edges joining any two of them are the same color. Then let $w_0=u_0dots u_{i_0}$, $w_1=u_{i_0+1}dots u_{i_1}$, etc.
$endgroup$
– bof
Jan 30 at 12:13
add a comment |
$begingroup$
Shouldn't $w_1w_2$, $w_2w_3$, $w_1w_2w_3$, $w_3w_4$, $w_2w_3w_4$, $w_1w_2w_3w_4$, $w_4w_5$, etc. also be the same color as $w_2$, $w_2$, $w_3$, etc.?
$endgroup$
– bof
Jan 30 at 9:52
$begingroup$
Isn't this a direct consequence of Ramsey's theorem?
$endgroup$
– bof
Jan 30 at 10:01
$begingroup$
@bof: No, why? $Chi$ is any colouring. My idea will be to have an infinite graphs with vertices $u_ildots u_j$ where $S=u_0u_1ldots$ and each $u_iin{0,1}$. $u_ildots u_j$ would be connected to $u_{j+1}ldots u_k$ by a directed edge colored "c" if $Chi(u_ildots u_j)=Chi(u_{j+1}ldots u_k)=c$. Probably some kind of Ramsey-like argument could be applied on that.
$endgroup$
– Faustus
Jan 30 at 10:02
1
$begingroup$
@Faustus My idea would be to consider a graph with vertices $0,1,2,3,dots$; for $ilt j$, vertices $i$ and $j$ would be joined by an edge of color $c$ if $chi(u_{i+1}u_{i+2}dots u_j)=c$. By Ramsey's theorem there is an infinite sequence $i_0lt i_1lt i_2ltcdots$ such that all edges joining any two of them are the same color. Then let $w_0=u_0dots u_{i_0}$, $w_1=u_{i_0+1}dots u_{i_1}$, etc.
$endgroup$
– bof
Jan 30 at 12:13
$begingroup$
Shouldn't $w_1w_2$, $w_2w_3$, $w_1w_2w_3$, $w_3w_4$, $w_2w_3w_4$, $w_1w_2w_3w_4$, $w_4w_5$, etc. also be the same color as $w_2$, $w_2$, $w_3$, etc.?
$endgroup$
– bof
Jan 30 at 9:52
$begingroup$
Shouldn't $w_1w_2$, $w_2w_3$, $w_1w_2w_3$, $w_3w_4$, $w_2w_3w_4$, $w_1w_2w_3w_4$, $w_4w_5$, etc. also be the same color as $w_2$, $w_2$, $w_3$, etc.?
$endgroup$
– bof
Jan 30 at 9:52
$begingroup$
Isn't this a direct consequence of Ramsey's theorem?
$endgroup$
– bof
Jan 30 at 10:01
$begingroup$
Isn't this a direct consequence of Ramsey's theorem?
$endgroup$
– bof
Jan 30 at 10:01
$begingroup$
@bof: No, why? $Chi$ is any colouring. My idea will be to have an infinite graphs with vertices $u_ildots u_j$ where $S=u_0u_1ldots$ and each $u_iin{0,1}$. $u_ildots u_j$ would be connected to $u_{j+1}ldots u_k$ by a directed edge colored "c" if $Chi(u_ildots u_j)=Chi(u_{j+1}ldots u_k)=c$. Probably some kind of Ramsey-like argument could be applied on that.
$endgroup$
– Faustus
Jan 30 at 10:02
$begingroup$
@bof: No, why? $Chi$ is any colouring. My idea will be to have an infinite graphs with vertices $u_ildots u_j$ where $S=u_0u_1ldots$ and each $u_iin{0,1}$. $u_ildots u_j$ would be connected to $u_{j+1}ldots u_k$ by a directed edge colored "c" if $Chi(u_ildots u_j)=Chi(u_{j+1}ldots u_k)=c$. Probably some kind of Ramsey-like argument could be applied on that.
$endgroup$
– Faustus
Jan 30 at 10:02
1
1
$begingroup$
@Faustus My idea would be to consider a graph with vertices $0,1,2,3,dots$; for $ilt j$, vertices $i$ and $j$ would be joined by an edge of color $c$ if $chi(u_{i+1}u_{i+2}dots u_j)=c$. By Ramsey's theorem there is an infinite sequence $i_0lt i_1lt i_2ltcdots$ such that all edges joining any two of them are the same color. Then let $w_0=u_0dots u_{i_0}$, $w_1=u_{i_0+1}dots u_{i_1}$, etc.
$endgroup$
– bof
Jan 30 at 12:13
$begingroup$
@Faustus My idea would be to consider a graph with vertices $0,1,2,3,dots$; for $ilt j$, vertices $i$ and $j$ would be joined by an edge of color $c$ if $chi(u_{i+1}u_{i+2}dots u_j)=c$. By Ramsey's theorem there is an infinite sequence $i_0lt i_1lt i_2ltcdots$ such that all edges joining any two of them are the same color. Then let $w_0=u_0dots u_{i_0}$, $w_1=u_{i_0+1}dots u_{i_1}$, etc.
$endgroup$
– bof
Jan 30 at 12:13
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%2f3093288%2fcolouring-a-sequence%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%2f3093288%2fcolouring-a-sequence%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$
Shouldn't $w_1w_2$, $w_2w_3$, $w_1w_2w_3$, $w_3w_4$, $w_2w_3w_4$, $w_1w_2w_3w_4$, $w_4w_5$, etc. also be the same color as $w_2$, $w_2$, $w_3$, etc.?
$endgroup$
– bof
Jan 30 at 9:52
$begingroup$
Isn't this a direct consequence of Ramsey's theorem?
$endgroup$
– bof
Jan 30 at 10:01
$begingroup$
@bof: No, why? $Chi$ is any colouring. My idea will be to have an infinite graphs with vertices $u_ildots u_j$ where $S=u_0u_1ldots$ and each $u_iin{0,1}$. $u_ildots u_j$ would be connected to $u_{j+1}ldots u_k$ by a directed edge colored "c" if $Chi(u_ildots u_j)=Chi(u_{j+1}ldots u_k)=c$. Probably some kind of Ramsey-like argument could be applied on that.
$endgroup$
– Faustus
Jan 30 at 10:02
1
$begingroup$
@Faustus My idea would be to consider a graph with vertices $0,1,2,3,dots$; for $ilt j$, vertices $i$ and $j$ would be joined by an edge of color $c$ if $chi(u_{i+1}u_{i+2}dots u_j)=c$. By Ramsey's theorem there is an infinite sequence $i_0lt i_1lt i_2ltcdots$ such that all edges joining any two of them are the same color. Then let $w_0=u_0dots u_{i_0}$, $w_1=u_{i_0+1}dots u_{i_1}$, etc.
$endgroup$
– bof
Jan 30 at 12:13