45816 - Henson Graphs & Frank Game. (avec P. Gazzano)

P. Gazzano, N. Lygeros

Rado Graph: countably graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge.

Robustness of Rado Graph: If a graph G is formed from the Rado graph by deleting any finite number of edges or vertices, or adding a finite number of edges, the change does not affect the extension property of the graph.

Hensen Graph: undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as induced subgraphs.

G3 is a triangle-free graph that contains all finite triangle free graphs.

If G3 is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs induced all i-clique-free finite graphs as induced subgraphs.

Now we consider the generalized Frank Game i.e. the board is Kn and not only K6. We are in the case of cooperation between the two players. At the end of the game, we have no triangle clique. We use all the possible configurations at each level Kn. Then we construct a sequence of all of them as class of Fraïssé. Each of the configurations of the two players can be considered as an element of the partition of the total game. In fact, these configuration are isomorphic. If we compute the Fraïssé limit of the configuration of the games of one player, we get the Henson Graph G3.