JournalsjemsOnline First

Consistent random vertex-orderings of graphs

  • Paul N. Balister

    University of Oxford, Oxford, UK

  • Béla Bollobás

    University of Cambridge, Cambridge, UK; University of Memphis, Memphis, USA

  • Svante Janson

    Uppsala University, Uppsala, Sweden
Consistent random vertex-orderings of graphs cover
Download PDF

A subscription is required to access this article.

Abstract

Given a hereditary graph property , consider distributions of random orderings of vertices of graphs that are preserved under isomorphisms and under taking induced subgraphs. We show that for many properties the only such random orderings are uniform, and give some examples of non-uniform orderings when they exist.

Cite this article

Paul N. Balister, Béla Bollobás, Svante Janson, Consistent random vertex-orderings of graphs. J. Eur. Math. Soc. (2025), published online first

DOI 10.4171/JEMS/1624