4
$\begingroup$

A Steiner triple system is a 3-uniform hypergraph in which every pair of vertices is contained in exactly one edge. A linear cycle (also called loose cycle) length $t$ consists of $2t$ cyclically ordered vertices and $t$ edges, each edge formed of 3 consecutive vertices, so that consecutive edges intersect in exactly one vertex. The linear path (also called loose path) can be defined in a similar way.

From the definitions, we can show that any Steiner triple system on $n$ vertices contains a linear path on at least $\frac{n+3}{2}$ vertices. My question is: what is the longest linear path in a Steiner triple system?

In precise, denoted by $\mathcal{S}_n$ the set of all Steiner triple systems on $n$ vertices, and let $p(S)$ (respectively, $c(S)$) be the number of vertices in a longest linear path (respectively, cycle) in a Steiner triple system $S$. Determine $\min_{S\in \mathcal{S}_n}p(S)$, $\max_{S\in \mathcal{S}_n}p(S)$, $\min_{S\in \mathcal{S}_n}c(S)$ and $\max_{S\in \mathcal{S}_n}c(S)$. Is there any results on these problems?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Do you know the values of $p$ and $c$ on some standard constructions of Steiner triples? $\endgroup$
    – Ilya Bogdanov
    Commented Oct 23, 2023 at 11:41
  • 1
    $\begingroup$ I think it's easy enough to show that there are infinitely many n for which there is an STS on n vertices with a linear path on n vertices. In the "doubling construction" you start with an STS on m vertices, call it S, and a complete graph on m+1 vertices (where m+1 is even). This complete graph has a proper edge coloring with m colors and I claim that it has a proper edge coloring with m colors in which there is a rainbow path of length m. Each vertex of S is associated with one color class from the complete graph and the rainbow path mentioned above gives the desired linear path in S. $\endgroup$
    – Louis D
    Commented Oct 23, 2023 at 15:43
  • $\begingroup$ (continued) I couldn't find a simple reference for the fact that every complete graph on m+1 vertices (with m+1 even) has a proper edge coloring with m colors in which there is a rainbow path of length m, but I am fairly confident this is true. $\endgroup$
    – Louis D
    Commented Oct 23, 2023 at 15:45
  • $\begingroup$ Sorry, I see that it is not true that if m+1 is even, then there is a proper edge coloring of K_{m+1} with m colors in which there is a rainbow path because this already fails when m+1=4. However, I'm still hopeful that it is true for large enough m or perhaps for m of a certain type. Either way, it is known that there is always a very long rainbow path (look up work on rainbow paths in properly edge colored complete graphs) in an even more general setting, so there are certainly infinitely many n for which there is a linear path covering (1-o(1))n vertices of S. $\endgroup$
    – Louis D
    Commented Oct 23, 2023 at 16:17
  • $\begingroup$ Gould, Kelly, Kühn, Osthus have shown that "most" proper edge-colourings of K_n admit rainbow Hamilton paths arxiv.org/abs/2007.00395 $\endgroup$
    – hdur
    Commented Oct 23, 2023 at 16:31

1 Answer 1

Reset to default
5
$\begingroup$

Im, Kim, Lee and Methuku have recently shown that one can find loose paths on $(1 - o(1))n$ vertices in any Steiner triple system on $n$ vertices. This is of course best possible up to the $o(1)$ term. In fact their result is more general and shows that STSs contain all almost-spanning "hypertrees".

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .