Disjoint systems

Noga Mordechai Alon, Benny Sudakov

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

Abstract

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
Pages159-163
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

Other

Other1st French-Israeli Workshop on Algebraic Coding, 1993
CountryFrance
CityParis
Period7/19/937/21/93

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Alon, N. M., & Sudakov, B. (1994). Disjoint systems. In Algebraic Coding - 1st French-Israeli Workshop, Proceedings (pp. 159-163). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 781 LNCS). Springer Verlag.