Problem #6

Is the (Triangle-Free) Henson Graph Pseudofinite?

Open!Ordinary impact — every problem listed here is a genuine, worthwhile open problem

Let H3H_3 be the (triangle-free) Henson graph: the countable, homogeneous, universal K3K_3-free graph. Is H3H_3 pseudofinite — that is, does every sentence true in H3H_3 also hold in some finite graph (equivalently, is H3H_3 elementarily equivalent to a structure arising as an ultraproduct of finite graphs)?

Reference for the problem statement

C. Ward Henson, A family of countable homogeneous graphs, Pacific Journal of Mathematics, 1971

Definitions

  • Henson graph H3H_3: the unique (up to isomorphism) countable graph that is homogeneous, triangle-free, and universal for countable triangle-free graphs — every countable triangle-free graph embeds into it.
  • Pseudofinite structure: a structure that is elementarily equivalent to an ultraproduct of finite structures (equivalently, every sentence true in it is true in some finite structure of the same signature).

Known Partial Results

  • The analogous question is resolved for the ordinary (triangle-permitting) random graph, which is pseudofinite.
  • Various structural and combinatorial properties of H3H_3 relevant to pseudofiniteness (e.g. related to Ramsey-type and homogeneity properties of K3K_3-free graphs) have been studied, but a resolution of pseudofiniteness itself remains open.

Notes

This question sits at the intersection of model theory and finite combinatorics/finite model theory, and is a natural test case for understanding which homogeneous structures built by Fraïssé-style constructions are pseudofinite.

Additional References

  • Henson, C. W. "A family of countable homogeneous graphs." Pacific Journal of Mathematics, 1971 (introduces the Henson graphs).
  • Various papers on pseudofinite structures and generalized Fraïssé constructions discuss this question; readers should consult recent model theory literature on pseudofiniteness for up-to-date status.

Comments

Loading comments…