Uniformly cross intersecting families

Details Uniformly cross intersecting families Uniformly cross intersecting families

2006-08-07

arxiv.org/abs/math/0608173v1

Mathematics

Combinatorics

Scientific paper

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 $\Theta(2^n)$, by Frankl and R\"{o}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}=\Theta(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.

Affiliated with

Also associated with

No associations

Rating

Uniformly cross intersecting families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Uniformly cross intersecting families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniformly cross intersecting families will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-601493