Disjoint systems

Noga Alon; Benny Sudakov

doi:10.1007/3-540-57843-9_17

Disjoint systems

Noga Alon, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A disjoint system of type (∀, ∃, k, n) is a collection C={A₁, …, A_m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair A_i and A_j of distinct members of C and for every A ∈ A_i there exists a B ∈ A_j that does not intersect A. Let D_n(∀, ∃, 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 language	English (US)
Title of host publication	Algebraic Coding - 1st French-Israeli Workshop, Proceedings
Editors	Gerard Cohen, Antoine Lobstein, Gilles Zemor, Simon Litsyn
Publisher	Springer Verlag
Pages	159-163
Number of pages	5
ISBN (Print)	9783540578437
DOIs	https://doi.org/10.1007/3-540-57843-9_17
State	Published - 1994
Externally published	Yes
Event	1st French-Israeli Workshop on Algebraic Coding, 1993 - Paris, France Duration: Jul 19 1993 → Jul 21 1993

Publication series

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

Other

Other	1st French-Israeli Workshop on Algebraic Coding, 1993
Country/Territory	France
City	Paris
Period	7/19/93 → 7/21/93

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-57843-9_17

Cite this

Alon, N., & Sudakov, B. (1994). Disjoint systems. In G. Cohen, A. Lobstein, G. Zemor, & S. Litsyn (Eds.), 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. https://doi.org/10.1007/3-540-57843-9_17

@inproceedings{c8b80fa4cb8a4127964b093880b73b0d,

title = "Disjoint systems",

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.",

author = "Noga Alon and Benny Sudakov",

year = "1994",

doi = "10.1007/3-540-57843-9_17",

language = "English (US)",

isbn = "9783540578437",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "159--163",

editor = "Gerard Cohen and Antoine Lobstein and Gilles Zemor and Simon Litsyn",

booktitle = "Algebraic Coding - 1st French-Israeli Workshop, Proceedings",

address = "Germany",

}

Alon, N & Sudakov, B 1994, Disjoint systems. in G Cohen, A Lobstein, G Zemor & S Litsyn (eds), Algebraic Coding - 1st French-Israeli Workshop, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 781 LNCS, Springer Verlag, pp. 159-163, 1st French-Israeli Workshop on Algebraic Coding, 1993, Paris, France, 7/19/93. https://doi.org/10.1007/3-540-57843-9_17

Disjoint systems. / Alon, Noga; Sudakov, Benny.
Algebraic Coding - 1st French-Israeli Workshop, Proceedings. ed. / Gerard Cohen; Antoine Lobstein; Gilles Zemor; Simon Litsyn. Springer Verlag, 1994. p. 159-163 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 781 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Disjoint systems

AU - Alon, Noga

AU - Sudakov, Benny

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85026852518&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85026852518&partnerID=8YFLogxK

U2 - 10.1007/3-540-57843-9_17

DO - 10.1007/3-540-57843-9_17

M3 - Conference contribution

AN - SCOPUS:85026852518

SN - 9783540578437

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 159

EP - 163

BT - Algebraic Coding - 1st French-Israeli Workshop, Proceedings

A2 - Cohen, Gerard

A2 - Lobstein, Antoine

A2 - Zemor, Gilles

A2 - Litsyn, Simon

PB - Springer Verlag

T2 - 1st French-Israeli Workshop on Algebraic Coding, 1993

Y2 - 19 July 1993 through 21 July 1993

ER -

Disjoint systems

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this