Set that doesn't shatter certain subsets












2












$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.










share|cite|improve this question











$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


















2












$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.










share|cite|improve this question











$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
















2












2








2





$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.










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 22 '18 at 15:10







user366818

















asked Dec 20 '18 at 13:47









user366818user366818

1,056511




1,056511












  • $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






  • 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












1 Answer
1






active

oldest

votes


















1












$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.






share|cite|improve this answer









$endgroup$














    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
    });


    }
    });














    draft saved

    draft discarded


















    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









    1












    $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.






    share|cite|improve this answer









    $endgroup$


















      1












      $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.






      share|cite|improve this answer









      $endgroup$
















        1












        1








        1





        $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.






        share|cite|improve this answer









        $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.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 22 '18 at 16:09









        Yuval FilmusYuval Filmus

        49k472148




        49k472148






























            draft saved

            draft discarded




















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            Plaza Victoria

            Puebla de Zaragoza

            Musa