Apparaît dans la collection : Model Theory and Combinatorics

An infinite graph is sparse if there is a positive integer k such that for every finite subgraph, the number of edges is bounded above by k times the number of vertices. Such graphs arise in model theory via Hrushovskis predimension constructions. In joint work with J. Hubicka and J. Nesetril, we study automorphism groups of sparse graphs from the viewpoint of topological dynamics and the Kechris, Pestov, Todorcevic correspondence. We investigate amenable and extremely amenable subgroups of these groups using the ‘space of k-orientations’ of the graph and results from structural Ramsey theory. In particular, we show that Hrushovskis example of an omega-categorical sparse graph has no omega-categorical expansion with an extremely amenable automorphism group, thereby providing a counterexample to a conjecture in the area.