5
$\begingroup$

I use the following Lemma and I wonder whether it is known in literature. If you look at the proof it feels like it should be known from combinatorics or extremal graph theory.

Lemma. Let $A$ be an $n$-element set and let $A_1,\ldots, A_n\subseteq A$ be a collection of sets, each of size at least $d$ such that $A=\bigcup_{1\leq i\leq n}A_i$. Let $d\leq s\leq n$. Then there exists a set $S\subseteq A$ of size $s$ such that $|A_i\cap S|\geq \left\lfloor sd/n\right\rfloor$ for at least $n/2$ of the $A_i$.

Proof. We may assume without loss of generality that every set $A_i$ has exactly $d$ elements. For each $i$, the number of subsets of $A$ of size $s$ including exactly $k$ elements of $A_i$ is $\binom{n-d}{s-k}\binom{d}{k}$ (choose $k$ elements of $A_i$ and $s-k$ elements of $A\setminus A_i$). Hence the number of subsets of $A$ of size $s$ including at least $k$ elements from $A_i$ is $\sum_{k\leq \ell}\binom{n-d}{s-\ell}\binom{d}{\ell}$.

For $k\leq d$ consider the bipartite graphs $G_k$, where one part consists of the $s$-element subsets of $A$ and the other part consists of the sets $A_i$. We introduce an edge between $(B, A_i)$ if and only if $|B\cap A_i|\geq k$. The degree of $B$ in $G_k$ corresponds to the number of $A_i$ that $B$ shares at least $k$ elements with. As observed above, every $A_i$ has degree $\sum_{k\leq \ell}\binom{n-d}{s-\ell}\binom{d}{\ell}$. Hence $|E(G_k)|=n\cdot \sum_{k\leq \ell}\binom{n-d}{s-\ell}\binom{d}{\ell}$. The average degree of a vertex $B$ in $G_k$ is $\frac{n\cdot\sum_{k\leq \ell} \binom{n-d}{s-\ell}\binom{d}{\ell}}{\binom{n}{s}}$ and there must be one vertex $S$ with at least this degree.

Observe that $\frac{\binom{n-d}{s-k}\binom{d}{k}}{\binom{n}{s}}$ is the probability mass function of a hypergeometric distribution with mean $\frac{ds}{n}$. Hence for $k=\left\lfloor\frac{ds}{n}\right\rfloor$ the above sum is greater than $1/2$ and hence $d(S)\geq n/2$ for this $k$. We conclude that $|A_i\cap S|=k=\left\lfloor\frac{ds}{n}\right\rfloor$ for at least $n/2$ of the $A_i$. $\hspace{4.5cm}\square$

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ there's probably a quick and dirty way of proving something along these lines using probabilistic method + markov inequality + poisson approximation, but I don't know if there's an official result of this kind. $\endgroup$ – Suresh Venkat Oct 31 '13 at 19:08
  • $\begingroup$ How do you know that the probability that a hypergeometric random variable is larger than its mean is at least $1/2$? In other words, how do you know that the median is smaller than the mean? $\endgroup$ – Yuval Filmus Nov 1 '13 at 0:30
  • $\begingroup$ @YuvalFilmus, the combinatorial meaning of mean and median is not relevant here. I am simply looking for a vertex with degree at least $n/2$, hence for the smallest value of $k$ such that the sum exceeds $1/2$. $\endgroup$ – Sebastian Siebertz Nov 3 '13 at 15:28

Your Answer

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

Browse other questions tagged or ask your own question.