Disjoint systems

Noga Alon; Benny Sudakov

doi:10.1002/rsa.3240060103

Disjoint systems

Noga Alon, Benny Sudakov

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

A disjoint system of type (∀, ∃, k, n) is a collection 𝒞 = {𝒜₁,…, 𝒜_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 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)
Pages (from-to)	13-20
Number of pages	8
Journal	Random Structures & Algorithms
Volume	6
Issue number	1
DOIs	https://doi.org/10.1002/rsa.3240060103
State	Published - Jan 1995
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1002/rsa.3240060103

Cite this

@article{37f6d40f8d3a4bd1a3a0bbc5e0859333,

title = "Disjoint systems",

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

author = "Noga Alon and Benny Sudakov",

year = "1995",

month = jan,

doi = "10.1002/rsa.3240060103",

language = "English (US)",

volume = "6",

pages = "13--20",

journal = "Random Structures & Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

number = "1",

}

TY - JOUR

T1 - Disjoint systems

AU - Alon, Noga

AU - Sudakov, Benny

PY - 1995/1

Y1 - 1995/1

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

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

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

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

U2 - 10.1002/rsa.3240060103

DO - 10.1002/rsa.3240060103

M3 - Article

AN - SCOPUS:84990652734

SN - 1042-9832

VL - 6

SP - 13

EP - 20

JO - Random Structures & Algorithms

JF - Random Structures & Algorithms

IS - 1

ER -

Disjoint systems

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this