Applying Dilworth's theorem to 50 intervals in R
$begingroup$
Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point.
I think it is quite obvious I need to apply Dilworth's theorem to my problem.
Let's denote the set of intervals by $I = {I_1, I_2,... , I_n }$. Define the partial order $preceq$ on $I$ so that $I_i preceq I_j$ if and only if one of the following holds:
- $I_i = I_j$
$I_i cap I_j = varnothing$ and $I_i$ is to the left of $I_j$, i.e.$forall x in I_i$ $forall y in I_j $ we have $x < y$.
$(I, preceq)$ is a poset.
By Dilworth’s theorem, we get that $(I, preceq)$ has either a chain of size $n$ or an antichain of size $sqrt n$. In the former case, we get $sqrt n$ pairwise disjoint intervals. In the latter case, we have a set of $sqrt n$ intervals $I'$ whose pairwise intersection is non-empty.
From there I don't really know what would be the next logical step.
combinatorics discrete-mathematics elementary-set-theory order-theory
edited Jan 23 at 11:30
zhoraster
15.9k21853
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
add a comment |
$begingroup$
Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point.
I think it is quite obvious I need to apply Dilworth's theorem to my problem.
Let's denote the set of intervals by $I = {I_1, I_2,... , I_n }$. Define the partial order $preceq$ on $I$ so that $I_i preceq I_j$ if and only if one of the following holds:
- $I_i = I_j$
$I_i cap I_j = varnothing$ and $I_i$ is to the left of $I_j$, i.e.$forall x in I_i$ $forall y in I_j $ we have $x < y$.
$(I, preceq)$ is a poset.
By Dilworth’s theorem, we get that $(I, preceq)$ has either a chain of size $n$ or an antichain of size $sqrt n$. In the former case, we get $sqrt n$ pairwise disjoint intervals. In the latter case, we have a set of $sqrt n$ intervals $I'$ whose pairwise intersection is non-empty.
From there I don't really know what would be the next logical step.
combinatorics discrete-mathematics elementary-set-theory order-theory
edited Jan 23 at 11:30
zhoraster
15.9k21853
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
2
$begingroup$
You suggested partial order is not, in fact, a partial order because it isn't antisymmetric. Consider two disjoint intervals.
$endgroup$
– saulspatz
Nov 7 '18 at 16:56
$begingroup$
It seems your condition 1 is redundant. I suspect that you meant $I_i = I_j$. Then the argument seems fine. It only misses this fact: if any two intervals intersect, then all of them intersect (which is easy to prove: consider the leftmost right end and the rightmost left end of the intervals).
$endgroup$
– zhoraster
Nov 7 '18 at 17:28
$begingroup$
@zhoraster Hi you are right it's $I_i = I_j$ for the first criteria. I am trying to understand the problem, English is not my language and the problem is written in English. What exactly is an interval of R?
$endgroup$
– NotAbelianGroup
Jan 16 at 16:43
$begingroup$
Interval is interval. $[a,b]$, $(a,b)$, $[a,b)$, or $(a,b]$.
$endgroup$
– zhoraster
Jan 23 at 11:29
$begingroup$
"chain or size $n$ or antichain of size $sqrt(n)$" looks like a typo; I think you mean chain of size $sqrt(n)$. What is the exact statement of Dilworth's theorem?
$endgroup$
– bof
Jan 23 at 12:29
add a comment |
$begingroup$
Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point.
I think it is quite obvious I need to apply Dilworth's theorem to my problem.
Let's denote the set of intervals by $I = {I_1, I_2,... , I_n }$. Define the partial order $preceq$ on $I$ so that $I_i preceq I_j$ if and only if one of the following holds:
- $I_i = I_j$
$I_i cap I_j = varnothing$ and $I_i$ is to the left of $I_j$, i.e.$forall x in I_i$ $forall y in I_j $ we have $x < y$.
$(I, preceq)$ is a poset.
By Dilworth’s theorem, we get that $(I, preceq)$ has either a chain of size $n$ or an antichain of size $sqrt n$. In the former case, we get $sqrt n$ pairwise disjoint intervals. In the latter case, we have a set of $sqrt n$ intervals $I'$ whose pairwise intersection is non-empty.
From there I don't really know what would be the next logical step.
combinatorics discrete-mathematics elementary-set-theory order-theory
edited Jan 23 at 11:30
zhoraster
15.9k21853
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
$endgroup$
Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point.
I think it is quite obvious I need to apply Dilworth's theorem to my problem.
Let's denote the set of intervals by $I = {I_1, I_2,... , I_n }$. Define the partial order $preceq$ on $I$ so that $I_i preceq I_j$ if and only if one of the following holds:
- $I_i = I_j$
$I_i cap I_j = varnothing$ and $I_i$ is to the left of $I_j$, i.e.$forall x in I_i$ $forall y in I_j $ we have $x < y$.
$(I, preceq)$ is a poset.
By Dilworth’s theorem, we get that $(I, preceq)$ has either a chain of size $n$ or an antichain of size $sqrt n$. In the former case, we get $sqrt n$ pairwise disjoint intervals. In the latter case, we have a set of $sqrt n$ intervals $I'$ whose pairwise intersection is non-empty.
From there I don't really know what would be the next logical step.
combinatorics discrete-mathematics elementary-set-theory order-theory
combinatorics discrete-mathematics elementary-set-theory order-theory
edited Jan 23 at 11:30
zhoraster
15.9k21853
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
edited Jan 23 at 11:30
zhoraster
15.9k21853
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
edited Jan 23 at 11:30
zhoraster
15.9k21853
edited Jan 23 at 11:30
zhoraster
15.9k21853
edited Jan 23 at 11:30
zhoraster
15.9k21853
15.9k21853
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
asked Nov 7 '18 at 16:50
NotAbelianGroupNotAbelianGroup
18211
18211
2
$begingroup$
You suggested partial order is not, in fact, a partial order because it isn't antisymmetric. Consider two disjoint intervals.
$endgroup$
– saulspatz
Nov 7 '18 at 16:56
$begingroup$
It seems your condition 1 is redundant. I suspect that you meant $I_i = I_j$. Then the argument seems fine. It only misses this fact: if any two intervals intersect, then all of them intersect (which is easy to prove: consider the leftmost right end and the rightmost left end of the intervals).
$endgroup$
– zhoraster
Nov 7 '18 at 17:28
$begingroup$
@zhoraster Hi you are right it's $I_i = I_j$ for the first criteria. I am trying to understand the problem, English is not my language and the problem is written in English. What exactly is an interval of R?
$endgroup$
– NotAbelianGroup
Jan 16 at 16:43
$begingroup$
Interval is interval. $[a,b]$, $(a,b)$, $[a,b)$, or $(a,b]$.
$endgroup$
– zhoraster
Jan 23 at 11:29
$begingroup$
"chain or size $n$ or antichain of size $sqrt(n)$" looks like a typo; I think you mean chain of size $sqrt(n)$. What is the exact statement of Dilworth's theorem?
$endgroup$
– bof
Jan 23 at 12:29
add a comment |
2
$begingroup$
You suggested partial order is not, in fact, a partial order because it isn't antisymmetric. Consider two disjoint intervals.
$endgroup$
– saulspatz
Nov 7 '18 at 16:56
$begingroup$
It seems your condition 1 is redundant. I suspect that you meant $I_i = I_j$. Then the argument seems fine. It only misses this fact: if any two intervals intersect, then all of them intersect (which is easy to prove: consider the leftmost right end and the rightmost left end of the intervals).
$endgroup$
– zhoraster
Nov 7 '18 at 17:28
$begingroup$
@zhoraster Hi you are right it's $I_i = I_j$ for the first criteria. I am trying to understand the problem, English is not my language and the problem is written in English. What exactly is an interval of R?
$endgroup$
– NotAbelianGroup
Jan 16 at 16:43
$begingroup$
Interval is interval. $[a,b]$, $(a,b)$, $[a,b)$, or $(a,b]$.
$endgroup$
– zhoraster
Jan 23 at 11:29
$begingroup$
"chain or size $n$ or antichain of size $sqrt(n)$" looks like a typo; I think you mean chain of size $sqrt(n)$. What is the exact statement of Dilworth's theorem?
$endgroup$
– bof
Jan 23 at 12:29
2
2
$begingroup$
You suggested partial order is not, in fact, a partial order because it isn't antisymmetric. Consider two disjoint intervals.
$endgroup$
– saulspatz
Nov 7 '18 at 16:56
$begingroup$
You suggested partial order is not, in fact, a partial order because it isn't antisymmetric. Consider two disjoint intervals.
$endgroup$
– saulspatz
Nov 7 '18 at 16:56
$begingroup$
It seems your condition 1 is redundant. I suspect that you meant $I_i = I_j$. Then the argument seems fine. It only misses this fact: if any two intervals intersect, then all of them intersect (which is easy to prove: consider the leftmost right end and the rightmost left end of the intervals).
$endgroup$
– zhoraster
Nov 7 '18 at 17:28
$begingroup$
It seems your condition 1 is redundant. I suspect that you meant $I_i = I_j$. Then the argument seems fine. It only misses this fact: if any two intervals intersect, then all of them intersect (which is easy to prove: consider the leftmost right end and the rightmost left end of the intervals).
$endgroup$
– zhoraster
Nov 7 '18 at 17:28
$begingroup$
@zhoraster Hi you are right it's $I_i = I_j$ for the first criteria. I am trying to understand the problem, English is not my language and the problem is written in English. What exactly is an interval of R?
$endgroup$
– NotAbelianGroup
Jan 16 at 16:43
$begingroup$
@zhoraster Hi you are right it's $I_i = I_j$ for the first criteria. I am trying to understand the problem, English is not my language and the problem is written in English. What exactly is an interval of R?
$endgroup$
– NotAbelianGroup
Jan 16 at 16:43
$begingroup$
Interval is interval. $[a,b]$, $(a,b)$, $[a,b)$, or $(a,b]$.
$endgroup$
– zhoraster
Jan 23 at 11:29
$begingroup$
Interval is interval. $[a,b]$, $(a,b)$, $[a,b)$, or $(a,b]$.
$endgroup$
– zhoraster
Jan 23 at 11:29
$begingroup$
"chain or size $n$ or antichain of size $sqrt(n)$" looks like a typo; I think you mean chain of size $sqrt(n)$. What is the exact statement of Dilworth's theorem?
$endgroup$
– bof
Jan 23 at 12:29
$begingroup$
"chain or size $n$ or antichain of size $sqrt(n)$" looks like a typo; I think you mean chain of size $sqrt(n)$. What is the exact statement of Dilworth's theorem?
$endgroup$
– bof
Jan 23 at 12:29
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%2f2988783%2fapplying-dilworths-theorem-to-50-intervals-in-r%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%2f2988783%2fapplying-dilworths-theorem-to-50-intervals-in-r%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
2
$begingroup$
You suggested partial order is not, in fact, a partial order because it isn't antisymmetric. Consider two disjoint intervals.
$endgroup$
– saulspatz
Nov 7 '18 at 16:56
$begingroup$
It seems your condition 1 is redundant. I suspect that you meant $I_i = I_j$. Then the argument seems fine. It only misses this fact: if any two intervals intersect, then all of them intersect (which is easy to prove: consider the leftmost right end and the rightmost left end of the intervals).
$endgroup$
– zhoraster
Nov 7 '18 at 17:28
$begingroup$
@zhoraster Hi you are right it's $I_i = I_j$ for the first criteria. I am trying to understand the problem, English is not my language and the problem is written in English. What exactly is an interval of R?
$endgroup$
– NotAbelianGroup
Jan 16 at 16:43
$begingroup$
Interval is interval. $[a,b]$, $(a,b)$, $[a,b)$, or $(a,b]$.
$endgroup$
– zhoraster
Jan 23 at 11:29
$begingroup$
"chain or size $n$ or antichain of size $sqrt(n)$" looks like a typo; I think you mean chain of size $sqrt(n)$. What is the exact statement of Dilworth's theorem?
$endgroup$
– bof
Jan 23 at 12:29