Say $E_1,...E_n\subset\{1,2,...,k\}= K$, each $|E_i|=4$ and each $j\in K$ appear in at most $3$ sets $E_i$.

Question

Say $E_1,...E_n\subset\{1,2,...,k\}= K$, each $|E_i|=4$ and each $j\in K$ appear in at most $3$ sets $E_i$. We choose from each $E_i$ one number. Prove that we can do that so that a set of all choosen numbers has not more than ${3k\over 7}$ members.

---

This was my try but the bound I get is not good and also I'm not even sure if it is correct.

We choose at random from each $E_i$ independently a number with a probability $p=1/4$ (so we can chose the same number more then once) and name this number $c_i$. Let $M$ be a set of choosen numbers and let $X=|M|$. If $X_i$ is indicator random variable for a number $i\in K$ then $$E(X) = E(X_1)+...+E(X_k)$$

Say $i$ is in a sets $E_1,...E_{d_i}$, where $d_i\leq 3$, then \begin{eqnarray}E(X_i) &=& P(X_i=1) \\ &=& P(\{i=c_1\}\cup ...\cup \{i=c_{d_i}\})\\ &=&1-P(\{i\ne c_1\}\cap ...\cap \{i\ne c_{d_i}\})\\ &=&1-P(i\ne c_1)\dots P(i\ne c_{d_i})\\ &=&1-\Big({3\over 4}\Big)^{d_i}\\ \end{eqnarray}

So we have $$E(X)= k-\sum _{i=1}^k\Big({3\over 4}\Big)^{d_i}\leq k-k\Big({3\over 4}\Big)^3$$

So $E(X) \leq {37k\over 64}$ which is not good enough.

---

Anyone solve this one with a probabilistic method gets bounty 500pt.

Answer 1

Here is an atempt with no sucsess. Any idea how to fix it?

Suppose we take each element from $K$ at random and independently with probability $p={3\over 7}$. Let $S$ be a set of a choosen elements. Then $|S|\leq {3k\over 7}$.

Let $X$ be a number of all sets among $E_1,...,E_n$ that intersection with $S$ is nonempty. We are interested if $P(X=n)>0$ i.e.

$$P((S\cap E_1 \ne \emptyset) \cap (S\cap E_2 \ne \emptyset)\cap...\cap (S\cap E_n \ne \emptyset))>0$$

which is the same as $$1>P((S\cap E_1 = \emptyset) \cup (S\cap E_2 =\emptyset)\cup...\cup (S\cap E_n = \emptyset))$$

Say $E_i=\{a,b,c,d\}$. Now we have $$\color{red}{P(S\cap E_i=\emptyset)= P(a\notin S\cap b\notin S\cap c\notin S\cap d\notin S) = ({4\over 7})^4}$$

(Is this correct?)

So we have by the union bound $$P(\bigcup _{i=1}^n S\cap E_i)\leq n ({4\over 7})^4 \leq {3k\over 4}({4\over 7})^4 $$

which is not good since it goes over $1$ (if $k\geq 22$). Any help here?

Answer 2

I really don't think a probabilistic argument would work. Take $m \ge 1, k = 4m, n = 3m$, and $A_1,A_2,A_3 = \{1,2,3,4\}, A_4,A_5,A_6 = \{5,6,7,8\}$, etc. Then we need at most $\frac{12}{7}m$ elements chosen, so on average we need a bit less than $2$ elements chosen from a batch of $3$. I don't see how a random choice will do this; the choices of elements from $A_2,A_3$ must depend on the choice of element from $A_1$. And once we start having these kinds of dependencies, the proof becomes much more combinatorial/deterministic and falls outside what any reasonable person would call a "probabilistic proof".

Note that the construction just mentioned rules out the probabilistic approach you outlined in the question. Indeed, $E(X)$ will be more than $\lfloor \frac{3k}{7} \rfloor$ ($m=1$ is easy to compute).

In regards to the approach you outlined in an answer, it nearly certainly is just as hard as the original approach. Indeed, it definitely will be true that $P(X=n) > 0$, since a valid choice of elements, one from each $E_i$, with size at most $\frac{3k}{7}$ could be the randomly chosen set $S$. The issue is that $P(X=n)$ will be exponentially small, and thus difficult to prove is nonzero. It will also be exponentially small even if we choose $X$ a bit more wisely, by, for example, choosing $i$ to be in $S$ with probability $\frac{3k}{7}\frac{\#\{1 \le j \le n : i \in A_j\}}{4n}$. I highly doubt there is any natural choice of probabilities that will yield $P(X=n)$ being not exponentially small.

Of course, there could be a completely different approach, that one would consider "probabilistic method" that does well with the construction mentioned at the beginning of my answer. However, I view that as unlikely, but I obviously cannot be sure.