Consistent random vertex-orderings of graphs

Paul N. Balister; Béla Bollobás; Svante Janson

doi:10.4171/jems/1624

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

Consistent random vertex-orderings of graphs

Paul N. Balister
University of Oxford, Oxford, UK
- MathSciNet
- ORCID
Béla Bollobás
University of Cambridge, Cambridge, UK; University of Memphis, Memphis, USA
Svante Janson
Uppsala University, Uppsala, Sweden
- MathSciNet
- ORCID

Download PDF

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

Abstract

Given a hereditary graph property $P$ , consider distributions of random orderings of vertices of graphs $G \in P$ that are preserved under isomorphisms and under taking induced subgraphs. We show that for many properties $P$ 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