Problem #6
Is the universal triangle free graph pseudofinite?
Let denote the universal triangle free graph, also known as the Henson graph. Is pseudofinite? More generally, is the universal -free graph pseudofinite for each ?
Definitions
- A graph omits a graph if is not isomorphic to any subgraph of . Note that this is weaker than requiring that is not isomorphic to any minor of .
- For any , the Henson graph denotes the universal -free graph, i.e. the unique-up-to-isomorphism countable graph which omits and into which every countable graph omitting embeds.
- A structure is pseudofinite if every first order sentence that it satisfies is also satisfied by some finite structure in the same signature. Equivalently, is elementarily equivalent to an ultraproduct of finite structures.
Notes
The Henson graphs were introduced in [Hen71]. This question is also considered an important open question in combinatorics.
Reference for the problem statement
[Che11]Gregory Cherlin, Two problems on homogeneous structures, revisited, Pacific Journal of Mathematics, 2011 [link] [doi]
Additional References
[Hen71]Henson, C. W., A family of countable homogeneous graphs, Pacific Journal of Mathematics, 1971
Loading comments…