12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – munchhausen Jun 21 '18 at 14:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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