6
$\begingroup$

What is the simplest isomorphism invariant which can distinguish between the two non-isomorphic Steiner triple systems on $13$ points?

Train structure and cycle structure, as described here, do the job, but is there a simple way? Maybe via $p$-ranks or something like that?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

Take the 26-vertex graphs whose vertices are the blocks and where two vertices are joined by an edge if the corresponding blocks have a vertex in common. These two graphs differ in many easily measured ways, for example having different numbers of induced cycles and different numbers of maximal independent sets. I suspect (but am too lazy to prove) that the two STSs have different numbers of Fano subplanes.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am probably missing something - but isn't counting maximal independent sets or induced cycles quite difficult? Wouldn't you have to list them before counting? Or is there a shortcut because of the special structure of the graph? $\endgroup$
    – Felix Goldberg
    Commented Mar 17, 2014 at 12:18
  • $\begingroup$ The independent sets will be quite small (at most 4), so it won't take long. You can even limit the size to the minimum that shows a difference and it will probably be even quicker. Don't bother making the graph I defined, just count sets of non-intersecting blocks. $\endgroup$
    – Brendan McKay
    Commented Mar 17, 2014 at 15:37
  • $\begingroup$ There are no proper subplanes (13 is too small). Am I missing something? $\endgroup$
    – Peter Dukes
    Commented Mar 19, 2014 at 17:29
  • $\begingroup$ @Peter: probably not, I was just guessing. $\endgroup$
    – Brendan McKay
    Commented Mar 19, 2014 at 19:02
6
$\begingroup$

There is a construction given in Theorem II.2.2.10 of the Handbook of Combinatorial designs for a STS of order a prime of form $6t+1$. It is clear that the resulting STS has a cyclic automorphism acting fixed-point-freely on points. The other STS of order 13 has a full automorphism group isomorphic to $S_{3}$. So the automorphism group could be a good invariant, depending on what you mean by simple.

Note that it is possible to label the blocks of the designs so that they differ in just six blocks (they differ by a switching operation). So it seems unlikely that a simple test which looks at local properties of an STS will be able to distinguish the two triple systems, though some less computationally expensive invariant may suffice in this small case.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can you please give me a reference for the six blocks difference fact? $\endgroup$
    – Felix Goldberg
    Commented Mar 17, 2014 at 1:14
  • $\begingroup$ Did you mean $S_{13}$ rather than $S_{3}$? $\endgroup$
    – Felix Goldberg
    Commented Mar 17, 2014 at 1:15
  • 2
    $\begingroup$ Both STS(13)'s are written out on page 29 of the Handbook of Combinatorial Designs. And no, the automorphism group of the second design is small, of order $6$. (It is easily seen that no non-trivial design with block size $k$ can have a $k$-transitive automorphism group.) $\endgroup$
    – Padraig Ó Catháin
    Commented Mar 17, 2014 at 1:58
0
$\begingroup$

Actually, I now know that perhaps the easiest way is to count the number of Pasch configurations - one of the STS(13) has thirteen of them and the other eight. (source)

Improve this answer
$\endgroup$

You must log in to answer this question.

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