Disjoint systems

Noga Alon, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


A disjoint system of type (∀, ∃, k, n) is a collection 𝒞 = {𝒜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 𝒞 and for every A ϵ 𝒜i there exists a B ϵ 𝒜j that does not intersect A. Let Dn (∀, ∃, k) denote the maximum possible cardinality of a disjoint system of type (∀, ∃, k, n). It is shown that for every fixed k ⩾ 2,. (Formula Presented.) This settles a problem of Ahlswede, Cai, and Zhang. Several related problems are considered as well.

Original languageEnglish (US)
Pages (from-to)13-20
Number of pages8
JournalRandom Structures & Algorithms
Issue number1
StatePublished - Jan 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Disjoint systems'. Together they form a unique fingerprint.

Cite this