On a conjecture of Erdős on locally sparse Steiner triple systems (Q2216922)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a conjecture of Erdős on locally sparse Steiner triple systems |
scientific article |
Statements
On a conjecture of Erdős on locally sparse Steiner triple systems (English)
0 references
18 December 2020
0 references
A partial Steiner triple system (PSTS) is a 3-uniform linear hypergraph. If it has \(n(n-1)/6\) triples (edges) and \(n\) vertices, then it is a Steiner triple system (STS). A \((j,\ell)\)-configuration in a PSTS is a set of \(\ell\) triples on \(j\) points. The girth of a PSTS is the smallest \(g\) such that the PSTS contains a \((g,g-2)\)-configuration. Alternative terminology is to say that a PSTS with girth (at least) \(g\) is \((g-3)\)-sparse.\par \textit{P. Erdős} [in: Colloquio internazionale sulle teorie combinatorie con la collaborazione della American Mathematical Society, Roma, 3--15 settembre 1973. Tomo II. Roma: Accademia Nazionale dei Lincei. 3--17 (1976; Zbl 0361.05037)] conjectured the existence of \(k\)-sparse STS for all large enough orders \(n\equiv1,3\mod6\). He also raised the question of whether \(k\)-sparse ``approximate'' STS can be found for all large enough orders. It is this question that the present paper answers. By analysing a triangle removal process the authors show that for every fixed \(k\) and large enough \(n\), there is a \(k\)-sparse PSTS on \(n\) vertices with \((1/6-o(1))n^2\) triples. The same result has been obtained independently by \textit{T. Bohman} and \textit{L. Warnke} [J. Lond. Math. Soc., II. Ser. 100, No. 3, 895--913 (2019; Zbl 1433.05050)].\par Historically, it took quite some effort to settle the existence of so-called anti-Pasch STS, which are precisely the \(4\)-sparse STS. Here it is conjectured that the number of anti-Pasch STS should be \((ne^{-9/4}+o(n))^{n^2/6}\).\par Generalisations on the main theme are considered. The primary challenge remains to resolve Erdős' conjecture for STS.
0 references
partial Steiner triple system
0 references
girth
0 references
sparse
0 references
forbidden configuration
0 references
triangle removal process
0 references
supermartingale
0 references
0 references