Domination problem with sets












12















Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:



(1) $|S_i|leq 3,i=1,2,...,k$



(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,S_k$.



Show that one can select $[frac{3k}{7}] $ sets from $S_1,...,S_k$
such that their union is $M$.






Partial solution: I can find a family of ${13over 25}k$ such sets that no element in $X$ is in more then 3 set from that family. Thus we have a family of the size ${13over 25}k$ instead of ${4over 7}k$.



Let' s take any set independently with a probability $p$. Let's mark with $X$ a number of a chosen sets and with $Y$ a number of elements that are ''bad''
i.e. elements which are in at least 4 sets among a chosen sets. Note that $4nleq 3k$. Then we have $$E(X-Y)=E(X)-E(Y) geq kp-np^4 geq kp (1-3p^3/4)$$Since a function $x mapsto x(1-3x^3/4)$ achives a maximum at $x=sqrt[3]{1/3}$ we have $E(X-Y)geq {sqrt[3]{9}over 4}k> {13over 25}k$.



So with the method of alteration we find constant ${sqrt[3]{9}over 4}$ which is about $0,051$ worse then ${4over 7}$.





The question is cross-posted to mathoverflow





For a full solution with probabilistic method I'm offering $color{red}{500}$ points of bounty at any time.










share|cite|improve this question
























  • Interesting. Also, I apologize for my earlier comment; I didn't understand til right now that you were throwing out sets instead of keeping them. I'm doubtful that a purely probabilistic proof of this fact exists, but I'll think about it
    – munchhausen
    Jun 21 '18 at 14:23
















12















Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:



(1) $|S_i|leq 3,i=1,2,...,k$



(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,S_k$.



Show that one can select $[frac{3k}{7}] $ sets from $S_1,...,S_k$
such that their union is $M$.






Partial solution: I can find a family of ${13over 25}k$ such sets that no element in $X$ is in more then 3 set from that family. Thus we have a family of the size ${13over 25}k$ instead of ${4over 7}k$.



Let' s take any set independently with a probability $p$. Let's mark with $X$ a number of a chosen sets and with $Y$ a number of elements that are ''bad''
i.e. elements which are in at least 4 sets among a chosen sets. Note that $4nleq 3k$. Then we have $$E(X-Y)=E(X)-E(Y) geq kp-np^4 geq kp (1-3p^3/4)$$Since a function $x mapsto x(1-3x^3/4)$ achives a maximum at $x=sqrt[3]{1/3}$ we have $E(X-Y)geq {sqrt[3]{9}over 4}k> {13over 25}k$.



So with the method of alteration we find constant ${sqrt[3]{9}over 4}$ which is about $0,051$ worse then ${4over 7}$.





The question is cross-posted to mathoverflow





For a full solution with probabilistic method I'm offering $color{red}{500}$ points of bounty at any time.










share|cite|improve this question
























  • Interesting. Also, I apologize for my earlier comment; I didn't understand til right now that you were throwing out sets instead of keeping them. I'm doubtful that a purely probabilistic proof of this fact exists, but I'll think about it
    – munchhausen
    Jun 21 '18 at 14:23














12












12








12


6






Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:



(1) $|S_i|leq 3,i=1,2,...,k$



(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,S_k$.



Show that one can select $[frac{3k}{7}] $ sets from $S_1,...,S_k$
such that their union is $M$.






Partial solution: I can find a family of ${13over 25}k$ such sets that no element in $X$ is in more then 3 set from that family. Thus we have a family of the size ${13over 25}k$ instead of ${4over 7}k$.



Let' s take any set independently with a probability $p$. Let's mark with $X$ a number of a chosen sets and with $Y$ a number of elements that are ''bad''
i.e. elements which are in at least 4 sets among a chosen sets. Note that $4nleq 3k$. Then we have $$E(X-Y)=E(X)-E(Y) geq kp-np^4 geq kp (1-3p^3/4)$$Since a function $x mapsto x(1-3x^3/4)$ achives a maximum at $x=sqrt[3]{1/3}$ we have $E(X-Y)geq {sqrt[3]{9}over 4}k> {13over 25}k$.



So with the method of alteration we find constant ${sqrt[3]{9}over 4}$ which is about $0,051$ worse then ${4over 7}$.





The question is cross-posted to mathoverflow





For a full solution with probabilistic method I'm offering $color{red}{500}$ points of bounty at any time.










share|cite|improve this question
















Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:



(1) $|S_i|leq 3,i=1,2,...,k$



(2) Any element of $M$ is an element of at least $4$ sets among
$S_1,....,S_k$.



Show that one can select $[frac{3k}{7}] $ sets from $S_1,...,S_k$
such that their union is $M$.






Partial solution: I can find a family of ${13over 25}k$ such sets that no element in $X$ is in more then 3 set from that family. Thus we have a family of the size ${13over 25}k$ instead of ${4over 7}k$.



Let' s take any set independently with a probability $p$. Let's mark with $X$ a number of a chosen sets and with $Y$ a number of elements that are ''bad''
i.e. elements which are in at least 4 sets among a chosen sets. Note that $4nleq 3k$. Then we have $$E(X-Y)=E(X)-E(Y) geq kp-np^4 geq kp (1-3p^3/4)$$Since a function $x mapsto x(1-3x^3/4)$ achives a maximum at $x=sqrt[3]{1/3}$ we have $E(X-Y)geq {sqrt[3]{9}over 4}k> {13over 25}k$.



So with the method of alteration we find constant ${sqrt[3]{9}over 4}$ which is about $0,051$ worse then ${4over 7}$.





The question is cross-posted to mathoverflow





For a full solution with probabilistic method I'm offering $color{red}{500}$ points of bounty at any time.







combinatorics algorithms extremal-combinatorics probabilistic-method






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 11 '18 at 5:41









zhoraster

15.7k21752




15.7k21752










asked Jul 14 '17 at 17:33









greedoidgreedoid

38.3k114797




38.3k114797












  • Interesting. Also, I apologize for my earlier comment; I didn't understand til right now that you were throwing out sets instead of keeping them. I'm doubtful that a purely probabilistic proof of this fact exists, but I'll think about it
    – munchhausen
    Jun 21 '18 at 14:23


















  • Interesting. Also, I apologize for my earlier comment; I didn't understand til right now that you were throwing out sets instead of keeping them. I'm doubtful that a purely probabilistic proof of this fact exists, but I'll think about it
    – munchhausen
    Jun 21 '18 at 14:23
















Interesting. Also, I apologize for my earlier comment; I didn't understand til right now that you were throwing out sets instead of keeping them. I'm doubtful that a purely probabilistic proof of this fact exists, but I'll think about it
– munchhausen
Jun 21 '18 at 14:23




Interesting. Also, I apologize for my earlier comment; I didn't understand til right now that you were throwing out sets instead of keeping them. I'm doubtful that a purely probabilistic proof of this fact exists, but I'll think about it
– munchhausen
Jun 21 '18 at 14:23










1 Answer
1






active

oldest

votes


















0














Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$.



Stage 1. Take maximal subfamily $mathcal{A} subseteq
{S_1,....,S_k} =:mathcal{S} $
such that:



$bullet$ every member of that family $mathcal{A}$ has 3 elements;



$bullet$ all sets in $mathcal{A}$ are disjunct.



Let $|mathcal{A}| =a$ and let $A= cup _{Xin mathcal{A}} X$.
Then $|A|=3a$. Now, since each $ain A$ appears exactly $4$ times
it must appear exactly $3$ times in sets not in $mathcal{A}$. So by double counting between $M$ and $mathcal{S}setminus mathcal{A}$ we have (elements in $A$ have a degree $3$ and other $4$) $$ 3cdot 3a +4(n-3a)leq 3cdot (k-a);;Longrightarrow ;;4n leq 3k;;;...(1)$$



Let us now erase all the elements in $M$ which appears in $A$ and let this new set be $M_1$, so $M_1 = Msetminus A$ (so $|M_1| = n-3a$) and do the same thing in remaining sets in $mathcal{S}setminus mathcal{A}$ and we get new family of sets $mathcal{S}_1$.



Notice that each element in $M_1$ appears still $4$ times in sets from $mathcal{S}_1$ and that each set in $mathcal{S}_1$ has at most $2$ elements. (Why? If some of it, say $X$, has $3$ elements, that means that no element in $X$ was erased, so no element in $X$ is in $A$. But then we could put $X$ in $mathcal{A}$ and we would get bigger family than $mathcal{A}$ which is already maximal.) Also, let $k_1=|mathcal{S}_1|$



Stage 2. Now take a maximal subfamily $mathcal{B} subseteq
mathcal{S}_1 $
such that:



$bullet$ every member of that family $mathcal{B}$ has 2 elements;



$bullet$ all sets in $mathcal{B}$ are disjunct.



Let $|mathcal{B}| =b$ and let $B= cup _{X in mathcal{B}} X$.
Then $|B|=2b$. Now, since each $bin B$ appears exactly $4$ times
it must appear exactly $3$ times in sets not in $mathcal{B}$. So by double counting between $M_1$ and $mathcal{S}_1setminus mathcal{B}$ we have (elements in $B$ have a degree $3$ and other $4$) $$ 3cdot 2b +4(n-3a-2b)leq 2cdot (k_1-b);;Longrightarrow ;;2n leq k+5a;;;...(2)$$



Let us now erase all the elements in $M_1$ which appears in $B$ and let this new set be $M_2$, so $M_2 = M_1setminus B$ (so $|M_2| =n-3a-2b$) and do the same thing in remaining sets in $mathcal{S}_1setminus mathcal{B}$ and we get new family of sets $mathcal{S}_2$.



Notice that each element in $M_2$ appears still 4 times in sets from $mathcal{S}_2$ and that each set in $mathcal{S}_2$ has at most 1 elements. (Why? If some of it, say $X$, has 2 elements, that means that no element in $X$ was erased, so no element in $X$ is in $B$. But then we could put $X$ in $mathcal{B}$ and we would get bigger family than $mathcal{B}$ which is already maximal.) Also, let $k_2=|mathcal{S}_2|$.



Final stage. Now take a maximal subfamily $mathcal{C} subseteq
mathcal{S}_2 $
such that:



$bullet$ every member of that family $mathcal{C}$ has 1 element;



$bullet$ all sets in $mathcal{C}$ are disjunct.



Let $|mathcal{C}| =c$ and let $C= cup _{X in mathcal{C}} X$.
Then $|C|=c$. Now, since each $cin C$ appears exactly 4 times
it must appear exactly 3 times in sets not in $mathcal{C}$. So by double counting between $M_2$ and $mathcal{S}_2setminus mathcal{C}$ we have (elements in $C$ have a degree $3$ and other $4$) $$ 3cdot c +4(n-3a-2b-c)leq 1cdot (k_2-c);;Longrightarrow ;;4n leq k+11a+7b;;;...(3)$$



Clearly $C=M_2$ so we are finish with the process, that is $c+2b+3a = |M| =n$. All we have to check if resurrected sets (that is, we refile all the sets with erased elements) satisfies $$a+b+cleq {3over 7}k;;;; {bf ?}$$



Using (1) and $3a+2b+c=n$ we get:
$$ 12a+8b+4cleq 3k$$
Using (2) and $3a+2b+c=n$ we get:
$$ a+4b+2cleq k$$
Using (3) and $3a+2b+c=n$ we get:
$$ 2a+2b+8cleq 2k$$
If we add these three inequalites we get
So $$ 14(a+b+c)<15a+14b+14cleq 6k$$ and thus a conclusion.






share|cite|improve this answer























    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%2f2358882%2fdomination-problem-with-sets%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









    0














    Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$.



    Stage 1. Take maximal subfamily $mathcal{A} subseteq
    {S_1,....,S_k} =:mathcal{S} $
    such that:



    $bullet$ every member of that family $mathcal{A}$ has 3 elements;



    $bullet$ all sets in $mathcal{A}$ are disjunct.



    Let $|mathcal{A}| =a$ and let $A= cup _{Xin mathcal{A}} X$.
    Then $|A|=3a$. Now, since each $ain A$ appears exactly $4$ times
    it must appear exactly $3$ times in sets not in $mathcal{A}$. So by double counting between $M$ and $mathcal{S}setminus mathcal{A}$ we have (elements in $A$ have a degree $3$ and other $4$) $$ 3cdot 3a +4(n-3a)leq 3cdot (k-a);;Longrightarrow ;;4n leq 3k;;;...(1)$$



    Let us now erase all the elements in $M$ which appears in $A$ and let this new set be $M_1$, so $M_1 = Msetminus A$ (so $|M_1| = n-3a$) and do the same thing in remaining sets in $mathcal{S}setminus mathcal{A}$ and we get new family of sets $mathcal{S}_1$.



    Notice that each element in $M_1$ appears still $4$ times in sets from $mathcal{S}_1$ and that each set in $mathcal{S}_1$ has at most $2$ elements. (Why? If some of it, say $X$, has $3$ elements, that means that no element in $X$ was erased, so no element in $X$ is in $A$. But then we could put $X$ in $mathcal{A}$ and we would get bigger family than $mathcal{A}$ which is already maximal.) Also, let $k_1=|mathcal{S}_1|$



    Stage 2. Now take a maximal subfamily $mathcal{B} subseteq
    mathcal{S}_1 $
    such that:



    $bullet$ every member of that family $mathcal{B}$ has 2 elements;



    $bullet$ all sets in $mathcal{B}$ are disjunct.



    Let $|mathcal{B}| =b$ and let $B= cup _{X in mathcal{B}} X$.
    Then $|B|=2b$. Now, since each $bin B$ appears exactly $4$ times
    it must appear exactly $3$ times in sets not in $mathcal{B}$. So by double counting between $M_1$ and $mathcal{S}_1setminus mathcal{B}$ we have (elements in $B$ have a degree $3$ and other $4$) $$ 3cdot 2b +4(n-3a-2b)leq 2cdot (k_1-b);;Longrightarrow ;;2n leq k+5a;;;...(2)$$



    Let us now erase all the elements in $M_1$ which appears in $B$ and let this new set be $M_2$, so $M_2 = M_1setminus B$ (so $|M_2| =n-3a-2b$) and do the same thing in remaining sets in $mathcal{S}_1setminus mathcal{B}$ and we get new family of sets $mathcal{S}_2$.



    Notice that each element in $M_2$ appears still 4 times in sets from $mathcal{S}_2$ and that each set in $mathcal{S}_2$ has at most 1 elements. (Why? If some of it, say $X$, has 2 elements, that means that no element in $X$ was erased, so no element in $X$ is in $B$. But then we could put $X$ in $mathcal{B}$ and we would get bigger family than $mathcal{B}$ which is already maximal.) Also, let $k_2=|mathcal{S}_2|$.



    Final stage. Now take a maximal subfamily $mathcal{C} subseteq
    mathcal{S}_2 $
    such that:



    $bullet$ every member of that family $mathcal{C}$ has 1 element;



    $bullet$ all sets in $mathcal{C}$ are disjunct.



    Let $|mathcal{C}| =c$ and let $C= cup _{X in mathcal{C}} X$.
    Then $|C|=c$. Now, since each $cin C$ appears exactly 4 times
    it must appear exactly 3 times in sets not in $mathcal{C}$. So by double counting between $M_2$ and $mathcal{S}_2setminus mathcal{C}$ we have (elements in $C$ have a degree $3$ and other $4$) $$ 3cdot c +4(n-3a-2b-c)leq 1cdot (k_2-c);;Longrightarrow ;;4n leq k+11a+7b;;;...(3)$$



    Clearly $C=M_2$ so we are finish with the process, that is $c+2b+3a = |M| =n$. All we have to check if resurrected sets (that is, we refile all the sets with erased elements) satisfies $$a+b+cleq {3over 7}k;;;; {bf ?}$$



    Using (1) and $3a+2b+c=n$ we get:
    $$ 12a+8b+4cleq 3k$$
    Using (2) and $3a+2b+c=n$ we get:
    $$ a+4b+2cleq k$$
    Using (3) and $3a+2b+c=n$ we get:
    $$ 2a+2b+8cleq 2k$$
    If we add these three inequalites we get
    So $$ 14(a+b+c)<15a+14b+14cleq 6k$$ and thus a conclusion.






    share|cite|improve this answer




























      0














      Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$.



      Stage 1. Take maximal subfamily $mathcal{A} subseteq
      {S_1,....,S_k} =:mathcal{S} $
      such that:



      $bullet$ every member of that family $mathcal{A}$ has 3 elements;



      $bullet$ all sets in $mathcal{A}$ are disjunct.



      Let $|mathcal{A}| =a$ and let $A= cup _{Xin mathcal{A}} X$.
      Then $|A|=3a$. Now, since each $ain A$ appears exactly $4$ times
      it must appear exactly $3$ times in sets not in $mathcal{A}$. So by double counting between $M$ and $mathcal{S}setminus mathcal{A}$ we have (elements in $A$ have a degree $3$ and other $4$) $$ 3cdot 3a +4(n-3a)leq 3cdot (k-a);;Longrightarrow ;;4n leq 3k;;;...(1)$$



      Let us now erase all the elements in $M$ which appears in $A$ and let this new set be $M_1$, so $M_1 = Msetminus A$ (so $|M_1| = n-3a$) and do the same thing in remaining sets in $mathcal{S}setminus mathcal{A}$ and we get new family of sets $mathcal{S}_1$.



      Notice that each element in $M_1$ appears still $4$ times in sets from $mathcal{S}_1$ and that each set in $mathcal{S}_1$ has at most $2$ elements. (Why? If some of it, say $X$, has $3$ elements, that means that no element in $X$ was erased, so no element in $X$ is in $A$. But then we could put $X$ in $mathcal{A}$ and we would get bigger family than $mathcal{A}$ which is already maximal.) Also, let $k_1=|mathcal{S}_1|$



      Stage 2. Now take a maximal subfamily $mathcal{B} subseteq
      mathcal{S}_1 $
      such that:



      $bullet$ every member of that family $mathcal{B}$ has 2 elements;



      $bullet$ all sets in $mathcal{B}$ are disjunct.



      Let $|mathcal{B}| =b$ and let $B= cup _{X in mathcal{B}} X$.
      Then $|B|=2b$. Now, since each $bin B$ appears exactly $4$ times
      it must appear exactly $3$ times in sets not in $mathcal{B}$. So by double counting between $M_1$ and $mathcal{S}_1setminus mathcal{B}$ we have (elements in $B$ have a degree $3$ and other $4$) $$ 3cdot 2b +4(n-3a-2b)leq 2cdot (k_1-b);;Longrightarrow ;;2n leq k+5a;;;...(2)$$



      Let us now erase all the elements in $M_1$ which appears in $B$ and let this new set be $M_2$, so $M_2 = M_1setminus B$ (so $|M_2| =n-3a-2b$) and do the same thing in remaining sets in $mathcal{S}_1setminus mathcal{B}$ and we get new family of sets $mathcal{S}_2$.



      Notice that each element in $M_2$ appears still 4 times in sets from $mathcal{S}_2$ and that each set in $mathcal{S}_2$ has at most 1 elements. (Why? If some of it, say $X$, has 2 elements, that means that no element in $X$ was erased, so no element in $X$ is in $B$. But then we could put $X$ in $mathcal{B}$ and we would get bigger family than $mathcal{B}$ which is already maximal.) Also, let $k_2=|mathcal{S}_2|$.



      Final stage. Now take a maximal subfamily $mathcal{C} subseteq
      mathcal{S}_2 $
      such that:



      $bullet$ every member of that family $mathcal{C}$ has 1 element;



      $bullet$ all sets in $mathcal{C}$ are disjunct.



      Let $|mathcal{C}| =c$ and let $C= cup _{X in mathcal{C}} X$.
      Then $|C|=c$. Now, since each $cin C$ appears exactly 4 times
      it must appear exactly 3 times in sets not in $mathcal{C}$. So by double counting between $M_2$ and $mathcal{S}_2setminus mathcal{C}$ we have (elements in $C$ have a degree $3$ and other $4$) $$ 3cdot c +4(n-3a-2b-c)leq 1cdot (k_2-c);;Longrightarrow ;;4n leq k+11a+7b;;;...(3)$$



      Clearly $C=M_2$ so we are finish with the process, that is $c+2b+3a = |M| =n$. All we have to check if resurrected sets (that is, we refile all the sets with erased elements) satisfies $$a+b+cleq {3over 7}k;;;; {bf ?}$$



      Using (1) and $3a+2b+c=n$ we get:
      $$ 12a+8b+4cleq 3k$$
      Using (2) and $3a+2b+c=n$ we get:
      $$ a+4b+2cleq k$$
      Using (3) and $3a+2b+c=n$ we get:
      $$ 2a+2b+8cleq 2k$$
      If we add these three inequalites we get
      So $$ 14(a+b+c)<15a+14b+14cleq 6k$$ and thus a conclusion.






      share|cite|improve this answer


























        0












        0








        0






        Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$.



        Stage 1. Take maximal subfamily $mathcal{A} subseteq
        {S_1,....,S_k} =:mathcal{S} $
        such that:



        $bullet$ every member of that family $mathcal{A}$ has 3 elements;



        $bullet$ all sets in $mathcal{A}$ are disjunct.



        Let $|mathcal{A}| =a$ and let $A= cup _{Xin mathcal{A}} X$.
        Then $|A|=3a$. Now, since each $ain A$ appears exactly $4$ times
        it must appear exactly $3$ times in sets not in $mathcal{A}$. So by double counting between $M$ and $mathcal{S}setminus mathcal{A}$ we have (elements in $A$ have a degree $3$ and other $4$) $$ 3cdot 3a +4(n-3a)leq 3cdot (k-a);;Longrightarrow ;;4n leq 3k;;;...(1)$$



        Let us now erase all the elements in $M$ which appears in $A$ and let this new set be $M_1$, so $M_1 = Msetminus A$ (so $|M_1| = n-3a$) and do the same thing in remaining sets in $mathcal{S}setminus mathcal{A}$ and we get new family of sets $mathcal{S}_1$.



        Notice that each element in $M_1$ appears still $4$ times in sets from $mathcal{S}_1$ and that each set in $mathcal{S}_1$ has at most $2$ elements. (Why? If some of it, say $X$, has $3$ elements, that means that no element in $X$ was erased, so no element in $X$ is in $A$. But then we could put $X$ in $mathcal{A}$ and we would get bigger family than $mathcal{A}$ which is already maximal.) Also, let $k_1=|mathcal{S}_1|$



        Stage 2. Now take a maximal subfamily $mathcal{B} subseteq
        mathcal{S}_1 $
        such that:



        $bullet$ every member of that family $mathcal{B}$ has 2 elements;



        $bullet$ all sets in $mathcal{B}$ are disjunct.



        Let $|mathcal{B}| =b$ and let $B= cup _{X in mathcal{B}} X$.
        Then $|B|=2b$. Now, since each $bin B$ appears exactly $4$ times
        it must appear exactly $3$ times in sets not in $mathcal{B}$. So by double counting between $M_1$ and $mathcal{S}_1setminus mathcal{B}$ we have (elements in $B$ have a degree $3$ and other $4$) $$ 3cdot 2b +4(n-3a-2b)leq 2cdot (k_1-b);;Longrightarrow ;;2n leq k+5a;;;...(2)$$



        Let us now erase all the elements in $M_1$ which appears in $B$ and let this new set be $M_2$, so $M_2 = M_1setminus B$ (so $|M_2| =n-3a-2b$) and do the same thing in remaining sets in $mathcal{S}_1setminus mathcal{B}$ and we get new family of sets $mathcal{S}_2$.



        Notice that each element in $M_2$ appears still 4 times in sets from $mathcal{S}_2$ and that each set in $mathcal{S}_2$ has at most 1 elements. (Why? If some of it, say $X$, has 2 elements, that means that no element in $X$ was erased, so no element in $X$ is in $B$. But then we could put $X$ in $mathcal{B}$ and we would get bigger family than $mathcal{B}$ which is already maximal.) Also, let $k_2=|mathcal{S}_2|$.



        Final stage. Now take a maximal subfamily $mathcal{C} subseteq
        mathcal{S}_2 $
        such that:



        $bullet$ every member of that family $mathcal{C}$ has 1 element;



        $bullet$ all sets in $mathcal{C}$ are disjunct.



        Let $|mathcal{C}| =c$ and let $C= cup _{X in mathcal{C}} X$.
        Then $|C|=c$. Now, since each $cin C$ appears exactly 4 times
        it must appear exactly 3 times in sets not in $mathcal{C}$. So by double counting between $M_2$ and $mathcal{S}_2setminus mathcal{C}$ we have (elements in $C$ have a degree $3$ and other $4$) $$ 3cdot c +4(n-3a-2b-c)leq 1cdot (k_2-c);;Longrightarrow ;;4n leq k+11a+7b;;;...(3)$$



        Clearly $C=M_2$ so we are finish with the process, that is $c+2b+3a = |M| =n$. All we have to check if resurrected sets (that is, we refile all the sets with erased elements) satisfies $$a+b+cleq {3over 7}k;;;; {bf ?}$$



        Using (1) and $3a+2b+c=n$ we get:
        $$ 12a+8b+4cleq 3k$$
        Using (2) and $3a+2b+c=n$ we get:
        $$ a+4b+2cleq k$$
        Using (3) and $3a+2b+c=n$ we get:
        $$ 2a+2b+8cleq 2k$$
        If we add these three inequalites we get
        So $$ 14(a+b+c)<15a+14b+14cleq 6k$$ and thus a conclusion.






        share|cite|improve this answer














        Clearly we can assume that each element in $M$ appears in exactly $4$ subsets. Let $|M| =n$.



        Stage 1. Take maximal subfamily $mathcal{A} subseteq
        {S_1,....,S_k} =:mathcal{S} $
        such that:



        $bullet$ every member of that family $mathcal{A}$ has 3 elements;



        $bullet$ all sets in $mathcal{A}$ are disjunct.



        Let $|mathcal{A}| =a$ and let $A= cup _{Xin mathcal{A}} X$.
        Then $|A|=3a$. Now, since each $ain A$ appears exactly $4$ times
        it must appear exactly $3$ times in sets not in $mathcal{A}$. So by double counting between $M$ and $mathcal{S}setminus mathcal{A}$ we have (elements in $A$ have a degree $3$ and other $4$) $$ 3cdot 3a +4(n-3a)leq 3cdot (k-a);;Longrightarrow ;;4n leq 3k;;;...(1)$$



        Let us now erase all the elements in $M$ which appears in $A$ and let this new set be $M_1$, so $M_1 = Msetminus A$ (so $|M_1| = n-3a$) and do the same thing in remaining sets in $mathcal{S}setminus mathcal{A}$ and we get new family of sets $mathcal{S}_1$.



        Notice that each element in $M_1$ appears still $4$ times in sets from $mathcal{S}_1$ and that each set in $mathcal{S}_1$ has at most $2$ elements. (Why? If some of it, say $X$, has $3$ elements, that means that no element in $X$ was erased, so no element in $X$ is in $A$. But then we could put $X$ in $mathcal{A}$ and we would get bigger family than $mathcal{A}$ which is already maximal.) Also, let $k_1=|mathcal{S}_1|$



        Stage 2. Now take a maximal subfamily $mathcal{B} subseteq
        mathcal{S}_1 $
        such that:



        $bullet$ every member of that family $mathcal{B}$ has 2 elements;



        $bullet$ all sets in $mathcal{B}$ are disjunct.



        Let $|mathcal{B}| =b$ and let $B= cup _{X in mathcal{B}} X$.
        Then $|B|=2b$. Now, since each $bin B$ appears exactly $4$ times
        it must appear exactly $3$ times in sets not in $mathcal{B}$. So by double counting between $M_1$ and $mathcal{S}_1setminus mathcal{B}$ we have (elements in $B$ have a degree $3$ and other $4$) $$ 3cdot 2b +4(n-3a-2b)leq 2cdot (k_1-b);;Longrightarrow ;;2n leq k+5a;;;...(2)$$



        Let us now erase all the elements in $M_1$ which appears in $B$ and let this new set be $M_2$, so $M_2 = M_1setminus B$ (so $|M_2| =n-3a-2b$) and do the same thing in remaining sets in $mathcal{S}_1setminus mathcal{B}$ and we get new family of sets $mathcal{S}_2$.



        Notice that each element in $M_2$ appears still 4 times in sets from $mathcal{S}_2$ and that each set in $mathcal{S}_2$ has at most 1 elements. (Why? If some of it, say $X$, has 2 elements, that means that no element in $X$ was erased, so no element in $X$ is in $B$. But then we could put $X$ in $mathcal{B}$ and we would get bigger family than $mathcal{B}$ which is already maximal.) Also, let $k_2=|mathcal{S}_2|$.



        Final stage. Now take a maximal subfamily $mathcal{C} subseteq
        mathcal{S}_2 $
        such that:



        $bullet$ every member of that family $mathcal{C}$ has 1 element;



        $bullet$ all sets in $mathcal{C}$ are disjunct.



        Let $|mathcal{C}| =c$ and let $C= cup _{X in mathcal{C}} X$.
        Then $|C|=c$. Now, since each $cin C$ appears exactly 4 times
        it must appear exactly 3 times in sets not in $mathcal{C}$. So by double counting between $M_2$ and $mathcal{S}_2setminus mathcal{C}$ we have (elements in $C$ have a degree $3$ and other $4$) $$ 3cdot c +4(n-3a-2b-c)leq 1cdot (k_2-c);;Longrightarrow ;;4n leq k+11a+7b;;;...(3)$$



        Clearly $C=M_2$ so we are finish with the process, that is $c+2b+3a = |M| =n$. All we have to check if resurrected sets (that is, we refile all the sets with erased elements) satisfies $$a+b+cleq {3over 7}k;;;; {bf ?}$$



        Using (1) and $3a+2b+c=n$ we get:
        $$ 12a+8b+4cleq 3k$$
        Using (2) and $3a+2b+c=n$ we get:
        $$ a+4b+2cleq k$$
        Using (3) and $3a+2b+c=n$ we get:
        $$ 2a+2b+8cleq 2k$$
        If we add these three inequalites we get
        So $$ 14(a+b+c)<15a+14b+14cleq 6k$$ and thus a conclusion.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 10 '18 at 16:25

























        answered Dec 9 '18 at 0:23









        greedoidgreedoid

        38.3k114797




        38.3k114797






























            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.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


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


            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%2f2358882%2fdomination-problem-with-sets%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

            Ellipse (mathématiques)

            Quarter-circle Tiles

            Mont Emei