Uniformly cross intersecting families
| dc.creator | Alon, Noga | |
| dc.creator | Lubetzky, Eyal | |
| dc.date | 2006-08-07 | |
| dc.date.accessioned | 2026-07-07T07:21:29Z | |
| dc.date.available | 2026-07-07T07:21:29Z | |
| dc.description | Let $\mathcal{A}$ and $\matchcal{B}$ denote two families of subsets of an $n$-element set. The pair $(\mathcal{A},\mathcal{B})$ is said to be $\ell$-cross-intersecting iff $|A\cap B| = \ell$ for all $A\in\mathcal{A}$ and $B\in\mathcal{B}$. Denote by $P_\ell(n)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ over all such pairs. The best known upper bound on $P_\ell(n)$ is $Θ(2^n)$, by Frankl and Rödl. For a lower bound, Ahlswede, Cai and Zhang showed, for all $n \geq 2\ell$, a simple construction of an $\ell$-cross-intersecting pair $(\mathcal{A},\mathcal{B})$ with $|\mathcal{A}||\mathcal{B}| = \binom{2\ell}{\ell}2^{n-2\ell}=Θ(2^n/\sqrt{\ell})$, and conjectured that this is best possible. Consequently, Sgall asked whether or not $P_\ell(n)$ decreases with $\ell$. In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large $\ell$, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of $\mathcal{A},\mathcal{B}$ over $\mathbb{R}$, we show that there exists some $\ell_0>0$, such that $P_\ell(n) \leq \binom{2\ell}{\ell}2^{n-2\ell}$ for all $\ell \geq \ell_0$. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum. | |
| dc.identifier | https://arxiv.org/abs/math/0608173 | |
| dc.identifier | http://arxiv.org/abs/math/0608173 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/115315 | |
| dc.subject | Combinatorics | |
| dc.title | Uniformly cross intersecting families | |
| dc.type | text |