On Systems of Small Sets with No Large Δ-Subsystems

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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)265-268
Number of pages4
JournalCombinatorics Probability and Computing
Issue number3
StatePublished - 1999
Externally publishedYes

ASJC Scopus subject areas

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


Dive into the research topics of 'On Systems of Small Sets with No Large Δ-Subsystems'. Together they form a unique fingerprint.

Cite this