MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\mathcal{T}$ and $\mathcal{S}$ be two families of subsets of $[n]$ such that for all $T_i\in \mathcal{T}$ and $S_j\in \mathcal{S}$,

  1. $|T_i \cap S_j| \neq\emptyset$
  2. $|T_i| , |S_j| \leq t = O(\log(n))$.

The union of the sets in $\mathcal{T}$ cover all of $[n]$, and likewise for $\mathcal{S}$, and $|\mathcal{T}| + |\mathcal{S}| \leq \mathrm{poly}(n)$. Furthermore, both $\mathcal{T}$ and $\mathcal{S}$ are Sperner families: no $T_i$ is a subset of another $T_j$, and no $S_i$ is a subset of another $S_j$.

Let us say that an element $k\in [n]$ is $\delta$-popular in $\mathcal{T}$ (resp. $\mathcal{S}$) if $k$ occurs in at least a $\delta$-fraction of the sets in $\mathcal{T}$ (resp. $\mathcal{S}$). The properties (1) and (2) above imply that every $T_i\in \mathcal{T}$ contains an element is $(1/t)$-popular in $\mathcal{S}$, and every $S_j\in\mathcal{S}$ contains an element that is $(1/t)$-popular in $\mathcal{T}$. My question is the following:

Is there always an element $k \in [n]$ that is $(1/o(t))$-popular in either $\mathcal{T}$ or $\mathcal{S}$?

For the application that I have in mind I may make one further assumption (which as far as I know, may not be necessary): for every $U\subseteq[n]$, either $T_i\subseteq U$ for some $T_i\in\mathcal{T}$, or $S_j\subseteq [n]\backslash U$ for some $S_j\in \mathcal{S}$.

share|cite|improve this question

The answer is NO without any of the two additional assumptions.

Consider a set of $(t-1)^2$ elements $A=\{a_{ij}\}_{i,j=1}^{t-1}\subset[n]$. Let each $T_k$ contain a "row" $R_i=\{a_{ij}\}_{j=1}^{t-1}$ and one additional element outside $A$, each row being assigned to almost the same number of $T_k$'s. Include also the sets $R_i$ into the family $\cal T$. Now let $$ {\cal S}=\bigl\{\{a_{1,i_1},\dots,a_{t,i_t}\} \;:\; i_1,\dots,i_t\in[t]\bigr\}. $$ Then these families are cross-intersecting. Next, $|{\cal T}|\leq n$, $|{\cal S}|=t^t$, and the maximal popularity is about $1/(t-1)$. Moreover, the second condition is satisfied: if $U$ does not contain any of $R_i$'s then $[n]\setminus U$ contains some element of $\cal S$.

In this example, $|{\cal S}|=t^t=n^{\log\log n}$ which is a bit larger than a polynomial. But in fact, if we omit the second assumption, then it suffices to take only $t$ sets into $\cal S$, namely the columns $C_j=\{a_{ij}\}_{i=1}^{t-1}$ (and remove $R_i$'s from $\cal T$ --- they are no more needed). Here the first additional assumption holds, but not the second one.

THis also shows that there is no hope for $O(1)$; namely, in the example above you may decrease $t$ a bit so that $t^t\leq poly(n)$.

PS. You may find useful to look at this paper by Zs. Tuza, especially its second section. For instance, one may derive from it the following.

If the sets $T_i$'s are independent with respect to the inclusion, then $|\cup {\cal T}|\leq \binom{2t}t$.

share|cite|improve this answer
Thanks Ilya, that's a nice example! I've edited the question accordingly (and also added two further assumptions that are okay for my application: $\mathcal{S}$ covers all of $[n]$ as well, and both $\mathcal{T}$ and $\mathcal{S}$ are independent families). – LYT Sep 7 '12 at 16:13
The fact that $\cal S$ covers $[n]$ follows from the last assumption. It IS NECESSARY because of an example with the columns! If $\cal T$ and $\cal S$ are independent, then I recommend you to read Tuza's paper - in any case, it might be helpful. – Ilya Bogdanov Sep 7 '12 at 17:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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