Ytukyg

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.

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.