Back to Search
Start Over
On a Conjecture of Erdős on Locally Sparse Steiner Triple Systems.
- Source :
- Combinatorica; Jun2020, Vol. 40 Issue 3, p363-403, 41p
- Publication Year :
- 2020
-
Abstract
- A famous theorem of Kirkman says that there exists a Steiner triple system of order n if and only if n ≡ 1,3 mod 6. 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- LOGICAL prediction
ARBITRARY constants
STEINER systems
Subjects
Details
- Language :
- English
- ISSN :
- 02099683
- Volume :
- 40
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Combinatorica
- Publication Type :
- Academic Journal
- Accession number :
- 144457395
- Full Text :
- https://doi.org/10.1007/s00493-019-4084-2