Partitions and orientations of the Rado graph
Résumé
We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs are the edgeless graph, the random tournament, the transitive tournaments of order type~$\omega^\alpha$, and two orientations of the Rado graph: the random oriented graph, and a newly found random acyclic oriented graph.
Domaines
Combinatoire [math.CO]
Loading...