### Abstract

Abstrac: 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 {pipe}A∩B{pipe} = ℓ for all A ∈ A and B ∈ B. Denote by P_{ℓ}(n) the maximum value of {pipe}A{pipe}{pipe}B{pipe} over all such pairs. The best known upper bound on P_{ℓ}(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, and conjectured that this is best possible. Consequently, Sgall asked whether or not P_{ℓ}(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, for all ℓ ≥ ℓ_{0}. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum.

Original language | English (US) |
---|---|

Pages (from-to) | 389-431 |

Number of pages | 43 |

Journal | Combinatorica |

Volume | 29 |

Issue number | 4 |

DOIs | |

State | Published - 2009 |

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Uniformly cross intersecting families'. Together they form a unique fingerprint.

## Cite this

*Combinatorica*,

*29*(4), 389-431. https://doi.org/10.1007/s00493-009-2332-6