Name
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 Θ(2n ), 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( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) $$2n−2ℓ = Θ(2n /$$ \sqrt \ell $$), and conjectured that this is best possible. Consequently, Sgall asked whether or not P e (n) decreases with ℓ. In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large ℓ, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of A,B over ℝ, we show that there exists some ℓ 0 0, such that P e (n) ≤ $$ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) $$2n−2ℓ for all ℓ≥ℓ 0. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00493-009-2332-6 | Combinatorica |
Keywords | Field | DocType |
maximum value,n-element set,characteristic vector,positive answer,cross-intersecting iff,b denote,cross-intersecting pair,linear space,b. denote,p e,lower bound,upper bound | Discrete mathematics,Combinatorics,Upper and lower bounds,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 0209-9683 |
Citations | PageRank | References |
1 | 0.35 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| Eyal Lubetzky | 2 | 355 | 28.87 |