Disjoint systems

Noga Alon, Benny Sudakov

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

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
Volume6
Issue number1
DOIs
StatePublished - Jan 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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

  • Cite this