<p>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. </p>

<p><strong>Lemma.</strong> 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$. </p>

<p><strong>Proof.</strong> 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}$. </p>

<p>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.</p>

<p>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$</p>

CC BY-SA 3.0
2013-10-31T19:08:28.567Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-11-01T00:30:32.823Z
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?
Yuval Filmus
CC BY-SA 3.0
2013-11-03T15:28:38.270Z
@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$.
Sebastian Siebertz
<reference-request><graph-theory><co.combinatorics>
Lemma about intersecting sets
Sebastian Siebertz
# Lemma about intersecting sets

(Asked by: username_0 on 2013-10-31)

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$

**Tags:** reference-request, graph-theory, co.combinatorics
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: @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$.  

---

## 0 answers

