Popular elements in cross-intersecting families - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:16:37Z http://mathoverflow.net/feeds/question/106542 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106542/popular-elements-in-cross-intersecting-families Popular elements in cross-intersecting families LYT 2012-09-06T20:38:05Z 2012-09-21T18:22:00Z <p>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}$, </p> <ol> <li>$|T_i \cap S_j| \neq\emptyset$</li> <li>$|T_i| , |S_j| \leq t = O(\log(n))$.</li> </ol> <p>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$. </p> <p>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: </p> <blockquote> <p>Is there always an element $k \in [n]$ that is $(1/o(t))$-popular in either $\mathcal{T}$ or $\mathcal{S}$? </p> </blockquote> <p>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}$. </p> http://mathoverflow.net/questions/106542/popular-elements-in-cross-intersecting-families/106573#106573 Answer by Ilya Bogdanov for Popular elements in cross-intersecting families Ilya Bogdanov 2012-09-07T06:24:50Z 2012-09-07T17:41:06Z <p>The answer is NO without any of the two additional assumptions.</p> <p>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$.</p> <p>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.</p> <p>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)$.</p> <p><b>PS.</b> You may find useful to look at <a href="http://www.sciencedirect.com/science/article/pii/0095895685900437" rel="nofollow">this paper by Zs. Tuza</a>, especially its second section. For instance, one may derive from it the following.</p> <p>If the sets $T_i$'s are independent with respect to the inclusion, then $|\cup {\cal T}|\leq \binom{2t}t$.</p>