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

DOI10.1002/RSA.20309MaRDI QIDQ3055899zbMATH OpenOpenAlexFDO

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

Publication date 10 November 2010

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

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

zbMATH Keywords

continuous graphsinvariant measuresrandomizationtriangle free graphsuniversal graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(15)

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