Problem #6
Is the (Triangle-Free) Henson Graph Pseudofinite?
Let be the (triangle-free) Henson graph: the countable, homogeneous, universal -free graph. Is pseudofinite — that is, does every sentence true in also hold in some finite graph (equivalently, is 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 : 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 relevant to pseudofiniteness (e.g. related to Ramsey-type and homogeneity properties of -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.
Loading comments…