Uniformly cross intersecting families |
| |
Authors: | Noga Alon Eyal Lubetzky |
| |
Affiliation: | 1.School of Mathematics,Institute for Advanced Study,Princeton,USA;2.Raymond and Beverly Sackler Faculty of Exact Sciences,Tel Aviv University,Tel Aviv,Israel;3.Theory Group of Microsoft Research,One Microsoft Way,Redmond,USA |
| |
Abstract: | Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P e (n) is Θ(2 n ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $
left( {{*{20}c}
{2ell }
ell
} right)
$
left( {begin{array}{*{20}c}
{2ell }
ell
end{array} } right)
2 n−2ℓ = Θ(2 n /$
sqrt ell
$
sqrt ell
), and conjectured that this is best possible. Consequently, Sgall asked whether or not P e (n) decreases with ℓ. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|