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.