Domination problem with sets

Question

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

For a solution using probabilistic method will be awarded with 200pt of bounty.

---

Alternative formulation.

Answer 1

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

Answer 2

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.

Answer 3

We give the bound $\frac{59}{140}k<\frac{3}{7}k$ by using a randomized algorithm introduced in the book ‘Probabilistic Method’ (Section 3.5) by Alon and Spencer.

Let $H=(M,\mathcal S)$ be a hypergraph, where $\{S_1,...,S_k\}=\mathcal S$. Assume each vertex appears in exactly $4$ hyperedges.

For each $S\in \mathcal S$, let $x_S$ be a uniform random label in the interval $[0,1]$, where all choices are independent. Note that with probability $1$, all labels are distinct.

The algorithm goes over the hyperedges in $\mathcal S$ by an increasing order of their labels, coloring each hyperedge blue, unless it contains an vertex in $M$ which is not covered yet.

When the algorithm end, the number (depends on all $x_v$, $v\in K$) of red hyperedges $X$ is an upper bound. Let's compute $\mathbb E X$.

A hyperedge $S$ is colored blue if and only if it is not the first hyperedge containing any $m\in S$. An hyperedge $S'$ lies behind $S$ when its label $x_{S'}>x_S$, which is of probability $1−x$. So $$\mathbb P(S \text{ is blue })\ge \int_0^1 (1-(1-x)^3)^3dx=\frac{81}{140}.$$

So $\mathbb EX\le \frac{59}{140}k$.

We note that this is the same as the bound given by the greedy algorithm and double counting by @nonuser and @Mark Dettinger