*Reference:*

Two problems on homogeneous structures,
revisited

in *Model Theoretic Methods in Finite Combinatorics,*
M. Grohe and J.A. Makowsky eds.,

Contemporary Mathematics, **558**, American Mathematical Society,
2011

A triangle free graph is called k-saturated if for every set S of at most k vertices, and for every independent subset T of S, there is at least 1 vertex adjacent to each vertex of T and to no vertex of S-T.

Problem: Is there a finite k-saturated triangle-free graph, for each k?

1. If one works with all graphs rather than triangle-free graphs, then one defines saturation similarly, omitting the condition that the subset T be independent. In this case such graphs exist by probabilistic arguments, and one may easily check that for each k, the property of k-saturation holds with asymptotic probability one. Probabilistic graph theorists have expressed interest in the problem in the triangle-free case but have not come up with anything directly relevant to date.

2. At the conference on distance regular graphs (Montreal 1996) I learned from Peter Cameron that in the strongly regular case 4-saturation can be excluded by a direct computation. On the other hand the most saturated finite triangle-free graph known is the Higman-Sims graph, which is 3-saturated with multiplicity 2 (meaning that two vertices of the specified type can always be found). Though there are infinite families of 3-saturated triangle-free graphs, the multiplicities are equal to 1 in all known cases.

Actually there are two relevant notions of multiplicity. Let us call the multiplicity of a 3-saturated graph its 3-multiplicity. Since a 3-saturated graph is also 2-saturated, it has a 2-multiplicity as well - the minimum number of vertices satisfying a given set of conditions relative to a pair of independent points. Or more simply, this is simply the minimum number of neighbors for a pair of independent vertices.

3. I would propose two specific instances of the problem, one vague and one quite precise (in two variants).A. Can one establish the nonexistence of k-saturated triangle free graphs for some k under weaker regularity hypotheses?

B. Can one find examples of triangle-free graphs which are either

(a) 3-saturated of unbounded 2-multiplicity?

or

(b) 3-saturated of 3-multiplicity 2 (and not Higman-Sims)?

*Note to B:* There are infinite families of 3-saturated
triangle-free graphs of
2-multiplicity 2. There are no known infinite families of 3-saturated
triangle-free graphs of 2-multiplicity greater than 2.
The Higman-Sims graph has 3-multiplicity 2, and 2-multiplicity 6.

Gregory Cherlin, cherlinmath.rutgers.edu