On large systems of sets with no large weak Δ-subsystems

A. V. Kostochka; V. Rödl

doi:10.1007/PL00009819

On large systems of sets with no large weak Δ-subsystems

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

Abstract

A family of sets is called a weak Δ-system if the cardinality of the intersection of any two sets is the same. We elaborate a construction by Rödl and Thoma [9] and show that for large n, there exists a family ℱ of subsets of {1, . . . , n} without weak Δ-systems of size 3 with \ℱ\ ≥ 2^{c(n log n)1/3}.

Original language	English (US)
Pages (from-to)	235-240
Number of pages	6
Journal	Combinatorica
Volume	18
Issue number	2
DOIs	https://doi.org/10.1007/PL00009819
State	Published - 1998
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Online availability

10.1007/PL00009819

Library availability

Discover UIUC Full Text

Cite this

@article{9ae0458643494910aa0fcb46f781f806,

title = "On large systems of sets with no large weak Δ-subsystems",

abstract = "A family of sets is called a weak Δ-system if the cardinality of the intersection of any two sets is the same. We elaborate a construction by R{\"o}dl and Thoma [9] and show that for large n, there exists a family ℱ of subsets of {1, . . . , n} without weak Δ-systems of size 3 with \ℱ\ ≥ 2c(n log n)1/3.",

author = "Kostochka, {A. V.} and V. R{\"o}dl",

note = "Funding Information: Mathematics Subject Classi cation (1991): 05D05 * This work was partially supported by the grant MR1-181 of the Cooperative Grant Program of the Civilian Research and Development Foundation and by the grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research. z This work partially supported by grant MR1-181 of the Civilian Research and Development Foundation and by NFS grant DMS 9704114.",

year = "1998",

doi = "10.1007/PL00009819",

language = "English (US)",

volume = "18",

pages = "235--240",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "2",

}

TY - JOUR

T1 - On large systems of sets with no large weak Δ-subsystems

AU - Kostochka, A. V.

AU - Rödl, V.

N1 - Funding Information: Mathematics Subject Classi cation (1991): 05D05 * This work was partially supported by the grant MR1-181 of the Cooperative Grant Program of the Civilian Research and Development Foundation and by the grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research. z This work partially supported by grant MR1-181 of the Civilian Research and Development Foundation and by NFS grant DMS 9704114.

PY - 1998

Y1 - 1998

N2 - A family of sets is called a weak Δ-system if the cardinality of the intersection of any two sets is the same. We elaborate a construction by Rödl and Thoma [9] and show that for large n, there exists a family ℱ of subsets of {1, . . . , n} without weak Δ-systems of size 3 with \ℱ\ ≥ 2c(n log n)1/3.

AB - A family of sets is called a weak Δ-system if the cardinality of the intersection of any two sets is the same. We elaborate a construction by Rödl and Thoma [9] and show that for large n, there exists a family ℱ of subsets of {1, . . . , n} without weak Δ-systems of size 3 with \ℱ\ ≥ 2c(n log n)1/3.

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

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

U2 - 10.1007/PL00009819

DO - 10.1007/PL00009819

M3 - Article

AN - SCOPUS:0039494922

SN - 0209-9683

VL - 18

SP - 235

EP - 240

JO - Combinatorica

JF - Combinatorica

IS - 2

ER -

On large systems of sets with no large weak Δ-subsystems

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this