Consistent random vertex-orderings of graphs
Given a hereditary graph property \mathcal{P} , consider distributions of random orderings of vertices of graphs G\in\mathcal{P} that are preserved under isomorphisms and under taking induced subgraphs. We show that for many properties \mathcal{P} the only such random orderings are uniform, and give some examples of non-uniform orderings when they exist.
Authors
- Paul Balister (ORCID: https://orcid.org/0000-0003-2696-0352)
- Svante Janson (ORCID: https://orcid.org/0000-0002-9680-2790)
- Béla Bollobás (ORCID: https://orcid.org/0000-0002-9819-7213)
Institutions
- Uppsala University (SE)
- University of Cambridge (GB)
- University of Oxford (GB)
- University of Memphis (US)
Publication Details
- Journal
- Journal of the European Mathematical Society
- Published
- 2025-03-27
- DOI
- https://doi.org/10.4171/jems/1624
- Primary Topic
- Graph theory and applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Microsoft Research
- University of Cambridge
- Knut och Alice Wallenbergs Stiftelse