Intersecting Systems

R. Ahlswede, N. Alon, P. L. Erdos, M. Ruszinkó, L. A. Székely

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


An intersecting system of type (∃, ∀, k, n) is a collection double-struck F sign = {ℱ1,...,ℱm} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair ℱi and ℱj of distinct members of double-struck F sign there exists an A ∈ ℱi that intersects every B ∈ ℱ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-1k-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.

Original languageEnglish (US)
Pages (from-to)127-137
Number of pages11
JournalCombinatorics Probability and Computing
Issue number2
StatePublished - 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Intersecting Systems'. Together they form a unique fingerprint.

Cite this