Consistent random vertex-orderings of graphs

Balister, Paul; Bollobás, Béla; Janson, Svante
Given a hereditary graph property {\$}\backslashmathcal{\{}P{\}}{\$}, consider distributions of random orderings of vertices of graphs {\$}G\backslashin\backslashmathcal{\{}P{\}}{\$} that are preserved under isomorphisms and under taking induced subgraphs. We show that for many properties {\$}\backslashmathcal{\{}P{\}}{\$} the only such random orderings are uniform, and give some examples of non-uniform orderings when they exist.
Research areas:
Year:
2015
Type of Publication:
Article
Number:
317532
Pages:
1-30
Hits: 3776

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information