On a conjecture of Erdős on locally sparse Steiner triple systems

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
129 Downloads (Pure)


A famous theorem of Kirkman says that there exists a Steiner triple system of order n if and only if n≡1,3mod6. In 1973, Erdős conjectured that one can find so-called `sparse' Steiner triple systems. Roughly speaking, the aim is to have at most j−3 triples on every set of j points, which would be best possible. (Triple systems with this sparseness property are also referred to as having high girth.) We prove this conjecture asymptotically by analysing a natural generalization of the triangle removal process. Our result also solves a problem posed by Lefmann, Phelps and Rödl as well as Ellis and Linial in a strong form, and answers a question of Krivelevich, Kwan, Loh, and Sudakov. Moreover, we pose a conjecture which would generalize the Erdős conjecture to Steiner systems with arbitrary parameters and provide some evidence for this.
Original languageEnglish
Pages (from-to)363-403
Number of pages41
Issue number3
Publication statusPublished - 28 Apr 2020

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'On a conjecture of Erdős on locally sparse Steiner triple systems'. Together they form a unique fingerprint.

Cite this