Disjoint systems

Noga Mordechai Alon, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A disjoint system of type (∀, ∃, k, n) is a collection C={A1, …, Am} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair Ai and Aj of distinct members of C and for every A ∈ Ai there exists a B ∈ Aj 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)
Title of host publicationAlgebraic Coding - 1st French-Israeli Workshop, Proceedings
PublisherSpringer Verlag
Number of pages5
ISBN (Print)9783540578437
StatePublished - Jan 1 1994
Externally publishedYes
Event1st French-Israeli Workshop on Algebraic Coding, 1993 - Paris, France
Duration: Jul 19 1993Jul 21 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume781 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st French-Israeli Workshop on Algebraic Coding, 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this