JournalsjemsVol. 27, No. 7pp. 2623–2652

Consistent random vertex-orderings of graphs

  • Paul N. Balister

    University of Oxford, Oxford, UK
    ORCID

  • Béla Bollobás

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

  • Svante Janson

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

This article is published open access under our Subscribe to Open model.

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. 27 (2025), no. 7, pp. 2623–2652

DOI 10.4171/JEMS/1624