An extremal problem for sets with applications to graph theory

Noga Alon

doi:10.1016/0097-3165(85)90048-2

An extremal problem for sets with applications to graph theory

Noga Alon

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

67 Scopus citations

Abstract

Let X₁, ..., X_n be n disjoint sets. For 1 ≤ i ≤ n and 1 ≤ j ≤ h let A_ij and B_ij be subsets of X_i that satisfy |A_ij| ≤ r_i and |B_ij| ≤ s_i for 1 ≤ i ≤ n, 1 ≤ j ≤ h, (∪_i A_ij) ∩ (∪_i B_ij) = {circled division slash} for 1 ≤ j ≤ h, (∪_i A_ij) ∩ (∪_i B_il) ≠ {circled division slash} for 1 ≤ j < l ≤ h. We prove that h≤ Π i=1 n r_i+s_i r_i. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).

Original language	English (US)
Pages (from-to)	82-89
Number of pages	8
Journal	Journal of Combinatorial Theory, Series A
Volume	40
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(85)90048-2
State	Published - Sep 1985
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0097-3165(85)90048-2

Cite this

@article{10b3651337a6480486aaadc3796a5d7e,

title = "An extremal problem for sets with applications to graph theory",

abstract = "Let X1, ..., Xn be n disjoint sets. For 1 ≤ i ≤ n and 1 ≤ j ≤ h let Aij and Bij be subsets of Xi that satisfy |Aij| ≤ ri and |Bij| ≤ si for 1 ≤ i ≤ n, 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bij) = \{circled division slash\} for 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bil) ≠ \{circled division slash\} for 1 ≤ j < l ≤ h. We prove that h≤ Π i=1 n ri+si ri. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).",

author = "Noga Alon",

year = "1985",

month = sep,

doi = "10.1016/0097-3165(85)90048-2",

language = "English (US)",

volume = "40",

pages = "82--89",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - An extremal problem for sets with applications to graph theory

AU - Alon, Noga

PY - 1985/9

Y1 - 1985/9

N2 - Let X1, ..., Xn be n disjoint sets. For 1 ≤ i ≤ n and 1 ≤ j ≤ h let Aij and Bij be subsets of Xi that satisfy |Aij| ≤ ri and |Bij| ≤ si for 1 ≤ i ≤ n, 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bij) = {circled division slash} for 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bil) ≠ {circled division slash} for 1 ≤ j < l ≤ h. We prove that h≤ Π i=1 n ri+si ri. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).

AB - Let X1, ..., Xn be n disjoint sets. For 1 ≤ i ≤ n and 1 ≤ j ≤ h let Aij and Bij be subsets of Xi that satisfy |Aij| ≤ ri and |Bij| ≤ si for 1 ≤ i ≤ n, 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bij) = {circled division slash} for 1 ≤ j ≤ h, (∪i Aij) ∩ (∪i Bil) ≠ {circled division slash} for 1 ≤ j < l ≤ h. We prove that h≤ Π i=1 n ri+si ri. This result is best possible and has some interesting consequences. Its proof uses multilinear techniques (exterior algebra).

UR - https://www.scopus.com/pages/publications/0442330916

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

U2 - 10.1016/0097-3165(85)90048-2

DO - 10.1016/0097-3165(85)90048-2

M3 - Article

AN - SCOPUS:0442330916

SN - 0097-3165

VL - 40

SP - 82

EP - 89

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

An extremal problem for sets with applications to graph theory

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this