Disjoint systems

Noga Alon, Benny Sudakov

Research output: Contribution to journal โ€บ Article โ€บ peer-review

3 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
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


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

Cite this