Uncountable graphs and invariant measures on the set of universal countable graphs

DOI10.1002/RSA.20309zbMATH Open1209.05158arXiv0804.3386OpenAlexW3083492539MaRDI QIDQ3055899FDOQ3055899

Authors: F. V. Petrov, A. M. Vershik 

Publication date: 10 November 2010

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We give new examples and describe the complete lists of all measures on the set of countable homogeneous universal graphs and $K_s$-free homogeneous universal graphs (for $sgeq3$) that are invariant with respect to the group of all permutations of the vertices. Such measures can be regarded as random graphs (respectively, random $K_s$-free graphs). The well-known example of Erd"os--R'enyi (ER) of the random graph corresponds to the Bernoulli measure on the set of adjacency matrices. For the case of the universal $K_s$-free graphs there were no previously known examples of the invariant measures on the space of such graphs. The main idea of our construction is based on the new notions of {it measurable universal}, and {it topologically universal} graphs, which are interesting themselves. The realization of the construction can be regarded as two-step randomization for universal measurable graph : {it "randomization in vertices"} and {it "randomization in edges"}. For $K_s$-free, $sgeq3$ there is only randomization in vertices of the measurable graphs. The completeness of our lists is proved using the important theorem by D. Aldous about $S_{infty}$-invariant matrices, which we reformulate in appropriate way.

Full work available at URL: https://arxiv.org/abs/0804.3386

Recommendations

• Measures on the Random Graph
• Invariant measures via inverse limits of finite structures
• There is no universal countable random-free graph
• On universal representation of random graphs
• Universality and randomness for the graphs and metric spaces

zbMATH Keywords

randomizationinvariant measuresuniversal graphstriangle free graphscontinuous graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Infinite graphs (05C63)

Cites Work

• Representations for partially exchangeable arrays of random variables
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Title not available (Why is that?)
• Classification of measurable functions of several variables and invariantly distributed random matrices
• Random metric spaces and universality
• Universal graphs and universal functions
• Homogeneous Cayley objects
• Probabilistic Symmetries and Invariance Principles
• Kolmogorov's Example (A Survey of Actions of Infinite-Dimensional Groups with an Invariant Probability Measure)
• A family of countable homogeneous graphs
• Globalization of the partial isometries of metric spaces and local approximation of the group of isometries of Urysohn space

Cited In (15)

• The countable character of uncountable graphs
• Semantic limits of dense combinatorial objects
• INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
• Instability, complexity, and evolution
• A graph-theoretic bound on the number of independent absolutely continuous invariant measures
• Random generations of the countable random graph
• Invariant measures via inverse limits of finite structures
• A classification of orbits admitting a unique invariant measure
• Relatively exchangeable structures
• Hadwiger's conjecture for uncountable graphs
• Invariance, quasi-invariance, and unimodularity for random graphs
• Martin-Löf randomness, invariant measures and countable homogeneous structures
• Measures on the Random Graph
• Graphs generated by measures
• Cohen-like first order structures

This page was built for publication: Uncountable graphs and invariant measures on the set of universal countable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3055899)