Canonical Ramsey theorem for graphs with clean intersections

Abstract

Extending earlier results of Nešetřil and Rödl [Selective graphs and hypergraphs, Ann. Discrete Math. 3 (1978), 181--189], we show that for every ordered graph $F$ there exist an ordered graph $H$ and a system ${\mathcal{H}}_F$ of induced copies of $F$ such that every colouring of the edges of $H$ yields a canonically coloured copy of $F$ from ${\mathcal{H}}_F$ and any two copies from ${\mathcal{H}}_F$ intersect either in a vertex or an edge or not at all. As a consequence, this allows us to construct, for any given ordered graph $F$, canonical Ramsey graphs $H$ enjoying additional structural properties. In particular, $H$ can have the same clique number as $F$ and, provided $F$ is not bipartite, the same odd girth. Moreover, if $F$ is connected, then the copies of $F$ from ${\mathcal{H}}_F$ are not only induced, but their pairs of vertices also have the same distances in $H$ as in $F$.

48 pages