For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond.

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 with probabilistic method: I can find a family of ${13\over 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 ${13\over 25}k$ instead of ${4\over 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 $4n\leq 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> {13\over 25}k$.

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


New contributor
greedoid is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • you can always post an answer to your own question – kodlu Dec 8 at 22:46

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 _{X\in \mathcal{A}} X$. Then $|A|=3a$. Now, since each $a\in 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$) $$ 3\cdot 3a +4(n-3a)\leq 3\cdot (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 = M\setminus 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 $b\in 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}_1\setminus \mathcal{B}$ we have (elements in $B$ have a degree $3$ and other $4$) $$ 3\cdot 2b +4(n-3a-2b)\leq 2\cdot (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_1\setminus B$ (so $|M_2| =n-3a-2b$) and do the same thing in remaining sets in $\mathcal{S}_1\setminus \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 $c\in 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}_2\setminus \mathcal{C}$ we have (elements in $C$ have a degree $3$ and other $4$) $$ 3\cdot c +4(n-3a-2b-c)\leq 1\cdot (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|$. All we have to check if resurrected sets (that is, we refile all the sets with erased elements) satisfies $$a+b+c\leq {3\over 7}k\;\;\;\; {\bf ?}$$

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

New contributor
greedoid is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    Brilliant solution! I had to think a while about the part with the "double counting", where you derive the equations (2) and (3), but understood it in the end. – Mark Dettinger Dec 9 at 17:18
  • 1
    If I am not mistaken, then the subfamilies that you select in stages 1 and 2 don't have to be maximal in a global sense. They just have to be maximal in the sense that it is impossible to add another disjoint set, right? So basically you can choose the sets randomly, and when you can no longer find a disjoint set of the required size, you proceed to the next stage. – Mark Dettinger Dec 9 at 17:31
  • 1
    I'm not sure what you meant by a global sense in first sentence, but the answer to the second one is yes.@MarkDettinger – greedoid Dec 9 at 17:36
  • 1
    You can think about this also algorithmicaly. Say $A$ is empty set in begining. Then you choose any set $S_i$ with 3 elements which are not in $A$ and put them in $A$ and you repeat that as long as you can. @MarkDettinger – greedoid Dec 9 at 17:41
  • 1
    I meant that it does not have to be the biggest possible subfamily. For example, if the only sets with three elements are {1,2,3}, {4,5,6}, and {2,3,4}, and you pick {2,3,4} first, you reach a local maximum and have to proceed to stage 2 immediately. The global maximum for stage 1 would have been a subfamily of size 2. However, even with a suboptimal first stage, you will still end up with a solution of size 3k/7 or less after the third stage. That's what I like about your algorithm. – Mark Dettinger Dec 9 at 18:05

59k/140 sets suffice

Using your three equations, it is possible to get an improved upper bound of $59k/140$ (instead of $3k/7 = 60k/140$).

$$12a+8b+4c \leq 3k$$ $$ a+4b+2c \leq k$$ $$ a+b+4c \leq k$$

Multiply the first equation by 9, the second one by 12, and the last one by 20.

$$108a+72b+36c \leq 27k$$ $$12a+48b+24c \leq 12k$$ $$20a+20b+80c \leq 20k$$

Then add them all and get:

$$140a+140b+140c \leq 59k$$ $$a+b+c \leq \frac{59}{140}k$$

This is the smallest solution that is attainable by combining the three equations. I found it by solving the linear optimization problem

$$3x_1 + x_2 + x_3 \rightarrow max$$ $$12x_1+x_2+x_3 \geq 1$$ $$8x_1+4x_2+x_3 \geq 1$$ $$4x_1+2x_2+4x_3 \geq 1$$

The optimal solution is $x_1=9/140, x_2=12/140, x_3=20/140$, which yields the factors for the optimal linear combination of the tree equations.

  • Great, thank you... – greedoid yesterday

Your Answer

greedoid is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.