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

randomizationinvariant measuresuniversal graphstriangle free graphscontinuous graphs

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• 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
• 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)

• Cohen-like first order structures
• The countable character of uncountable graphs
• Semantic limits of dense combinatorial objects
• Instability, complexity, and evolution
• INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES
• 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

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)