Set that doesn't shatter certain subsets
$begingroup$
Let $Asubset mathcal{P}({1, dots, n}) $ and $ B subset {1, dots, n }$
We say $A$ shatters $B$ if $forall y subset B, exists x in A$ such that $x cap B = y$.
I am asked to show that if $A$ does not shatter the sets: ${1,2,3},{2,3,4}, dots, {n-2,n-1,n,}, {n-1,n,1}, {n,1,2}$ and $n$ is a multiple of $3$ then $|A| leq 7^{frac{n}{3}}$
My current thinking is that, for each of these $3$-sets, we have to miss at least one of their subsets.
Specifically, for each $a subset {x,y,z}$ there are $2^{n-3}$ subsets of ${1,dots,n}$ that intersect with ${x,y,z}$ to give $a$. (Call the set of there $2^{n-3}$ subsets $C_{{x,y,z}}(a)$) Hence if $A$ does not shatter ${1,2,3}$ because we are missing $a$, then $A$ cannot contain these $2^{n-3}$ subsets.
I want to say that there is some subset $B subset mathcal{P}({1,dots,n}$ of size $8* 7^{frac{n}{3}}$ such that we must have $A subset B$, and we may only have at most $frac{7}{8}$ of the elements of $B$. I suspect we have something like:
$B = bigcup_{{x,y,z} text{ mentioned earlier}}bigcup_{a subset {x,y,z}} C_{{x,y,z}}(a)$
However, at this point I am stuck and I'm not sure how to proceed. I can't think of a nice way to count the size of $B$ and show it is what I want because I can't think of an easy way to account for all of the overlaps occurring.
combinatorics elementary-set-theory
asked Dec 20 '18 at 13:47
user366818user366818
949410
$endgroup$
add a comment |
$begingroup$
Let $Asubset mathcal{P}({1, dots, n}) $ and $ B subset {1, dots, n }$
We say $A$ shatters $B$ if $forall y subset B, exists x in A$ such that $x cap B = y$.
I am asked to show that if $A$ does not shatter the sets: ${1,2,3},{2,3,4}, dots, {n-2,n-1,n,}, {n-1,n,1}, {n,1,2}$ and $n$ is a multiple of $3$ then $|A| leq 7^{frac{n}{3}}$
My current thinking is that, for each of these $3$-sets, we have to miss at least one of their subsets.
Specifically, for each $a subset {x,y,z}$ there are $2^{n-3}$ subsets of ${1,dots,n}$ that intersect with ${x,y,z}$ to give $a$. (Call the set of there $2^{n-3}$ subsets $C_{{x,y,z}}(a)$) Hence if $A$ does not shatter ${1,2,3}$ because we are missing $a$, then $A$ cannot contain these $2^{n-3}$ subsets.
I want to say that there is some subset $B subset mathcal{P}({1,dots,n}$ of size $8* 7^{frac{n}{3}}$ such that we must have $A subset B$, and we may only have at most $frac{7}{8}$ of the elements of $B$. I suspect we have something like:
$B = bigcup_{{x,y,z} text{ mentioned earlier}}bigcup_{a subset {x,y,z}} C_{{x,y,z}}(a)$
However, at this point I am stuck and I'm not sure how to proceed. I can't think of a nice way to count the size of $B$ and show it is what I want because I can't think of an easy way to account for all of the overlaps occurring.
combinatorics elementary-set-theory
asked Dec 20 '18 at 13:47
user366818user366818
949410
$endgroup$
$begingroup$
Since $mathcal{P}({1, dots, n})$ is a family of (non-empty) subsets of ${1, dots, n}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right?
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:43
2
$begingroup$
Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $Bsubset B$ so there exists $xsubset A$ such that $xcap B=B$, that is $xsupset B$. So $Asupset B$. Conversely, if $Asupset B$ than for any $ysubset B$ we have $ysubset A$ so if we put $x=y$ then $xcap B=y$. That is $A$ shatters $B$ iff $Asupset B$.
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:44
$begingroup$
@AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y subset B ; exists x in A$ such that $x cap B = y$
$endgroup$
– user366818
Dec 22 '18 at 15:11
add a comment |
$begingroup$
Let $Asubset mathcal{P}({1, dots, n}) $ and $ B subset {1, dots, n }$
We say $A$ shatters $B$ if $forall y subset B, exists x in A$ such that $x cap B = y$.
I am asked to show that if $A$ does not shatter the sets: ${1,2,3},{2,3,4}, dots, {n-2,n-1,n,}, {n-1,n,1}, {n,1,2}$ and $n$ is a multiple of $3$ then $|A| leq 7^{frac{n}{3}}$
My current thinking is that, for each of these $3$-sets, we have to miss at least one of their subsets.
Specifically, for each $a subset {x,y,z}$ there are $2^{n-3}$ subsets of ${1,dots,n}$ that intersect with ${x,y,z}$ to give $a$. (Call the set of there $2^{n-3}$ subsets $C_{{x,y,z}}(a)$) Hence if $A$ does not shatter ${1,2,3}$ because we are missing $a$, then $A$ cannot contain these $2^{n-3}$ subsets.
I want to say that there is some subset $B subset mathcal{P}({1,dots,n}$ of size $8* 7^{frac{n}{3}}$ such that we must have $A subset B$, and we may only have at most $frac{7}{8}$ of the elements of $B$. I suspect we have something like:
$B = bigcup_{{x,y,z} text{ mentioned earlier}}bigcup_{a subset {x,y,z}} C_{{x,y,z}}(a)$
However, at this point I am stuck and I'm not sure how to proceed. I can't think of a nice way to count the size of $B$ and show it is what I want because I can't think of an easy way to account for all of the overlaps occurring.
combinatorics elementary-set-theory
asked Dec 20 '18 at 13:47
user366818user366818
949410
$endgroup$
Let $Asubset mathcal{P}({1, dots, n}) $ and $ B subset {1, dots, n }$
We say $A$ shatters $B$ if $forall y subset B, exists x in A$ such that $x cap B = y$.
I am asked to show that if $A$ does not shatter the sets: ${1,2,3},{2,3,4}, dots, {n-2,n-1,n,}, {n-1,n,1}, {n,1,2}$ and $n$ is a multiple of $3$ then $|A| leq 7^{frac{n}{3}}$
My current thinking is that, for each of these $3$-sets, we have to miss at least one of their subsets.
Specifically, for each $a subset {x,y,z}$ there are $2^{n-3}$ subsets of ${1,dots,n}$ that intersect with ${x,y,z}$ to give $a$. (Call the set of there $2^{n-3}$ subsets $C_{{x,y,z}}(a)$) Hence if $A$ does not shatter ${1,2,3}$ because we are missing $a$, then $A$ cannot contain these $2^{n-3}$ subsets.
I want to say that there is some subset $B subset mathcal{P}({1,dots,n}$ of size $8* 7^{frac{n}{3}}$ such that we must have $A subset B$, and we may only have at most $frac{7}{8}$ of the elements of $B$. I suspect we have something like:
$B = bigcup_{{x,y,z} text{ mentioned earlier}}bigcup_{a subset {x,y,z}} C_{{x,y,z}}(a)$
However, at this point I am stuck and I'm not sure how to proceed. I can't think of a nice way to count the size of $B$ and show it is what I want because I can't think of an easy way to account for all of the overlaps occurring.
combinatorics elementary-set-theory
combinatorics elementary-set-theory
asked Dec 20 '18 at 13:47
user366818user366818
949410
asked Dec 20 '18 at 13:47
user366818user366818
949410
edited Dec 22 '18 at 15:10
user366818
asked Dec 20 '18 at 13:47
user366818user366818
949410
asked Dec 20 '18 at 13:47
user366818user366818
949410
asked Dec 20 '18 at 13:47
user366818user366818
949410
949410
$begingroup$
Since $mathcal{P}({1, dots, n})$ is a family of (non-empty) subsets of ${1, dots, n}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right?
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:43
2
$begingroup$
Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $Bsubset B$ so there exists $xsubset A$ such that $xcap B=B$, that is $xsupset B$. So $Asupset B$. Conversely, if $Asupset B$ than for any $ysubset B$ we have $ysubset A$ so if we put $x=y$ then $xcap B=y$. That is $A$ shatters $B$ iff $Asupset B$.
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:44
$begingroup$
@AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y subset B ; exists x in A$ such that $x cap B = y$
$endgroup$
– user366818
Dec 22 '18 at 15:11
add a comment |
$begingroup$
Since $mathcal{P}({1, dots, n})$ is a family of (non-empty) subsets of ${1, dots, n}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right?
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:43
2
$begingroup$
Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $Bsubset B$ so there exists $xsubset A$ such that $xcap B=B$, that is $xsupset B$. So $Asupset B$. Conversely, if $Asupset B$ than for any $ysubset B$ we have $ysubset A$ so if we put $x=y$ then $xcap B=y$. That is $A$ shatters $B$ iff $Asupset B$.
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:44
$begingroup$
@AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y subset B ; exists x in A$ such that $x cap B = y$
$endgroup$
– user366818
Dec 22 '18 at 15:11
$begingroup$
Since $mathcal{P}({1, dots, n})$ is a family of (non-empty) subsets of ${1, dots, n}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right?
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:43
$begingroup$
Since $mathcal{P}({1, dots, n})$ is a family of (non-empty) subsets of ${1, dots, n}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right?
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:43
2
2
$begingroup$
Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $Bsubset B$ so there exists $xsubset A$ such that $xcap B=B$, that is $xsupset B$. So $Asupset B$. Conversely, if $Asupset B$ than for any $ysubset B$ we have $ysubset A$ so if we put $x=y$ then $xcap B=y$. That is $A$ shatters $B$ iff $Asupset B$.
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:44
$begingroup$
Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $Bsubset B$ so there exists $xsubset A$ such that $xcap B=B$, that is $xsupset B$. So $Asupset B$. Conversely, if $Asupset B$ than for any $ysubset B$ we have $ysubset A$ so if we put $x=y$ then $xcap B=y$. That is $A$ shatters $B$ iff $Asupset B$.
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:44
$begingroup$
@AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y subset B ; exists x in A$ such that $x cap B = y$
$endgroup$
– user366818
Dec 22 '18 at 15:11
$begingroup$
@AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y subset B ; exists x in A$ such that $x cap B = y$
$endgroup$
– user366818
Dec 22 '18 at 15:11
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Consider the $n/3$ sets
$$
{1,2,3},{4,5,6},ldots,{n-2,n-1,n}.
$$
Since $A$ doesn't shatter ${1,2,3}$, there exists some subset $T_{123}$ such that $S cap {1,2,3} neq T_{123}$ for all $S in A$. Define $T_{456},ldots$ similarly. Then
$$
A subseteq [mathcal{P}({1,2,3}) setminus {T_{123}}] times [mathcal{P}({4,5,6}) setminus {T_{456}}] times cdots times [mathcal{P}({n-2,n-1,n}) setminus {T_{n-2,n-1,n}}].
$$
Each of the $n/3$ factors on the right-hand side contains $2^3-1=7$ elements, and so the right-hand side consists of $7^{n/3}$ sets.
When $n > 3$, this bound isn't tight, since the right-hand side does shatter all other adjacent triplets.
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
$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%2f3047554%2fset-that-doesnt-shatter-certain-subsets%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$
Consider the $n/3$ sets
$$
{1,2,3},{4,5,6},ldots,{n-2,n-1,n}.
$$
Since $A$ doesn't shatter ${1,2,3}$, there exists some subset $T_{123}$ such that $S cap {1,2,3} neq T_{123}$ for all $S in A$. Define $T_{456},ldots$ similarly. Then
$$
A subseteq [mathcal{P}({1,2,3}) setminus {T_{123}}] times [mathcal{P}({4,5,6}) setminus {T_{456}}] times cdots times [mathcal{P}({n-2,n-1,n}) setminus {T_{n-2,n-1,n}}].
$$
Each of the $n/3$ factors on the right-hand side contains $2^3-1=7$ elements, and so the right-hand side consists of $7^{n/3}$ sets.
When $n > 3$, this bound isn't tight, since the right-hand side does shatter all other adjacent triplets.
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
$endgroup$
add a comment |
$begingroup$
Consider the $n/3$ sets
$$
{1,2,3},{4,5,6},ldots,{n-2,n-1,n}.
$$
Since $A$ doesn't shatter ${1,2,3}$, there exists some subset $T_{123}$ such that $S cap {1,2,3} neq T_{123}$ for all $S in A$. Define $T_{456},ldots$ similarly. Then
$$
A subseteq [mathcal{P}({1,2,3}) setminus {T_{123}}] times [mathcal{P}({4,5,6}) setminus {T_{456}}] times cdots times [mathcal{P}({n-2,n-1,n}) setminus {T_{n-2,n-1,n}}].
$$
Each of the $n/3$ factors on the right-hand side contains $2^3-1=7$ elements, and so the right-hand side consists of $7^{n/3}$ sets.
When $n > 3$, this bound isn't tight, since the right-hand side does shatter all other adjacent triplets.
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
$endgroup$
add a comment |
$begingroup$
Consider the $n/3$ sets
$$
{1,2,3},{4,5,6},ldots,{n-2,n-1,n}.
$$
Since $A$ doesn't shatter ${1,2,3}$, there exists some subset $T_{123}$ such that $S cap {1,2,3} neq T_{123}$ for all $S in A$. Define $T_{456},ldots$ similarly. Then
$$
A subseteq [mathcal{P}({1,2,3}) setminus {T_{123}}] times [mathcal{P}({4,5,6}) setminus {T_{456}}] times cdots times [mathcal{P}({n-2,n-1,n}) setminus {T_{n-2,n-1,n}}].
$$
Each of the $n/3$ factors on the right-hand side contains $2^3-1=7$ elements, and so the right-hand side consists of $7^{n/3}$ sets.
When $n > 3$, this bound isn't tight, since the right-hand side does shatter all other adjacent triplets.
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
$endgroup$
Consider the $n/3$ sets
$$
{1,2,3},{4,5,6},ldots,{n-2,n-1,n}.
$$
Since $A$ doesn't shatter ${1,2,3}$, there exists some subset $T_{123}$ such that $S cap {1,2,3} neq T_{123}$ for all $S in A$. Define $T_{456},ldots$ similarly. Then
$$
A subseteq [mathcal{P}({1,2,3}) setminus {T_{123}}] times [mathcal{P}({4,5,6}) setminus {T_{456}}] times cdots times [mathcal{P}({n-2,n-1,n}) setminus {T_{n-2,n-1,n}}].
$$
Each of the $n/3$ factors on the right-hand side contains $2^3-1=7$ elements, and so the right-hand side consists of $7^{n/3}$ sets.
When $n > 3$, this bound isn't tight, since the right-hand side does shatter all other adjacent triplets.
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
answered Dec 22 '18 at 16:09
Yuval FilmusYuval Filmus
48.5k471144
48.5k471144
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%2f3047554%2fset-that-doesnt-shatter-certain-subsets%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$
Since $mathcal{P}({1, dots, n})$ is a family of (non-empty) subsets of ${1, dots, n}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right?
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:43
2
$begingroup$
Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $Bsubset B$ so there exists $xsubset A$ such that $xcap B=B$, that is $xsupset B$. So $Asupset B$. Conversely, if $Asupset B$ than for any $ysubset B$ we have $ysubset A$ so if we put $x=y$ then $xcap B=y$. That is $A$ shatters $B$ iff $Asupset B$.
$endgroup$
– Alex Ravsky
Dec 21 '18 at 3:44
$begingroup$
@AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y subset B ; exists x in A$ such that $x cap B = y$
$endgroup$
– user366818
Dec 22 '18 at 15:11