Popular elements in cross-intersecting families

2012-09-06T20:38:05Z

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}$,

$|T_i \cap S_j| \neq\emptyset$
$|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}$.

Answer by Ilya Bogdanov for Popular elements in cross-intersecting families

2012-09-07T06:24:50Z

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$.

Popular elements in cross-intersecting families - MathOverflow

Popular elements in cross-intersecting families

Answer by Ilya Bogdanov for Popular elements in cross-intersecting families