Article contents
Intersecting Systems
Published online by Cambridge University Press: 01 June 1997
Abstract
An intersecting system of type (∃, ∀, k, n) is a collection [ ]={[Fscr ]1, ..., [Fscr ]m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair [Fscr ]i and [Fscr ]j of distinct members of [ ] there exists an A∈[Fscr ]i that intersects every B∈[Fscr ]j. Let In (∃, ∀, k) denote the maximum possible cardinality of an intersecting system of type (∃, ∀, k, n). Ahlswede, Cai and Zhang conjectured that for every k≥1, there exists an n0(k) so that In (∃, ∀, k)=(n−1/k−1) for all n>n0(k). Here we show that this is true for k≤3, but false for all k≥8. We also prove some related results.
- Type
- Research Article
- Information
- Copyright
- 1997 Cambridge University Press
- 2
- Cited by