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.
4. This problem arises in model theory, as one of the simplest cases of a problem involving the approximation of infinite structures by finite ones. It seems likely that any progress on the more general problem will require techniques for dealing with this concrete case.
math.rutgers.edu