On Systems of Small Sets with No Large Δ-Subsystems

A. V. Kostochka; V. Rödl; L. A. Talysheva

doi:10.1017/S0963548399003818

On Systems of Small Sets with No Large Δ-Subsystems

A. V. Kostochka, V. Rödl, L. A. Talysheva

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

Abstract

A family of k sets is called a Δ-system if any two sets have the same intersection. Denote by f(r,k) the least integer so that any r-uniform family of f(r,k) sets contains a Δ-system consisting of k sets. We prove that, for every fixed r, f(r,k) = k^r + o(k^r). Using a recent result of Molloy and Reed [5], a bound on the error term is provided for sufficiently large k.

Original language	English (US)
Pages (from-to)	265-268
Number of pages	4
Journal	Combinatorics Probability and Computing
Volume	8
Issue number	3
DOIs	https://doi.org/10.1017/S0963548399003818
State	Published - 1999
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Online availability

10.1017/S0963548399003818

Library availability

Discover UIUC Full Text

Cite this

@article{7c2bb48ef28145fd8582ad08f9b306b9,

title = "On Systems of Small Sets with No Large Δ-Subsystems",

abstract = "A family of k sets is called a Δ-system if any two sets have the same intersection. Denote by f(r,k) the least integer so that any r-uniform family of f(r,k) sets contains a Δ-system consisting of k sets. We prove that, for every fixed r, f(r,k) = kr + o(kr). Using a recent result of Molloy and Reed [5], a bound on the error term is provided for sufficiently large k.",

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

year = "1999",

doi = "10.1017/S0963548399003818",

language = "English (US)",

volume = "8",

pages = "265--268",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - On Systems of Small Sets with No Large Δ-Subsystems

AU - Kostochka, A. V.

AU - Rödl, V.

AU - Talysheva, L. A.

PY - 1999

Y1 - 1999

N2 - A family of k sets is called a Δ-system if any two sets have the same intersection. Denote by f(r,k) the least integer so that any r-uniform family of f(r,k) sets contains a Δ-system consisting of k sets. We prove that, for every fixed r, f(r,k) = kr + o(kr). Using a recent result of Molloy and Reed [5], a bound on the error term is provided for sufficiently large k.

AB - A family of k sets is called a Δ-system if any two sets have the same intersection. Denote by f(r,k) the least integer so that any r-uniform family of f(r,k) sets contains a Δ-system consisting of k sets. We prove that, for every fixed r, f(r,k) = kr + o(kr). Using a recent result of Molloy and Reed [5], a bound on the error term is provided for sufficiently large k.

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

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

U2 - 10.1017/S0963548399003818

DO - 10.1017/S0963548399003818

M3 - Article

AN - SCOPUS:0442311736

SN - 0963-5483

VL - 8

SP - 265

EP - 268

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -

On Systems of Small Sets with No Large Δ-Subsystems

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this