# Domination problem with sets

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

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.

• 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

This is algorithmic solution:

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| =n$$. 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 So $$14(a+b+c)<15a+14b+14c\leq 6k$$ and thus a conclusion.