×

Steiner triple systems and existentially closed graphs. (English) Zbl 1075.05012

A graph is \(n\)-existentially closed if, for every \(n\)-subset \(S\) of the vertex set, for every subset \(T\) of \(S\), there is at least one vertex not in \(S\) adjacent to all vertices in \(T\) but none in \(S \setminus T\). When is the block intersection graph of a Steiner triple system of order \(v\) (STS\((v)\)) an \(n\)-existentially closed graph? It is proved that a block intersection graph of an STS\((v)\) is 2-existentially closed if and only if \(v \geq 13\). Turning to 3-existentially closed block intersection graphs, all orders except for \(v \in \{19,21\}\) are ruled out. It is shown that at least two STS(19)s have block intersection graphs that are 3-existentially closed; the case \(v=21\) is not resolved.

MSC:

05B07 Triple systems