Problem #6

Is the universal triangle free graph pseudofinite?

Open!!High impact — resolution would likely be publishable in a top journal (Advances-level or above)

Let H3\mathcal{H}_3 denote the universal triangle free graph, also known as the Henson graph. Is H3\mathcal{H}_3 pseudofinite? More generally, is the universal KnK_n-free graph pseudofinite for each nn?

Definitions

  • A graph GG omits a graph HH if HH is not isomorphic to any subgraph of GG. Note that this is weaker than requiring that HH is not isomorphic to any minor of GG.
  • For any n>2n > 2, the Henson graph Hn\mathcal{H}_n denotes the universal KnK_n-free graph, i.e. the unique-up-to-isomorphism countable graph which omits KnK_n and into which every countable graph omitting KnK_n embeds.
  • A structure AA is pseudofinite if every first order sentence that it satisfies is also satisfied by some finite structure in the same signature. Equivalently, AA 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

Comments

Loading comments…