Subgraph densities in Markov spaces

DOI10.1016/J.AIM.2023.109414MaRDI QIDQ6184559zbMATH OpenFDO

Authors Dávid Kunszenti-Kovács, Balázs Szegedy, László Lovász

Publication date 25 January 2024

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph limitsubgraph densityMarkov space

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial probability (60C05)

Abstract: We generalize subgraph densities, arising in dense graph limit theory, to Markov spaces (symmetric measures on the square of a standard Borel space). More generally, we define an analogue of the set of homomorphisms in the form of a measure on maps of a finite graph into a Markov space. The existence of such homomorphism measures is not always guaranteed, but can be established under rather natural smoothness conditions on the Markov space and sparseness conditions on the graph. This continues a direction in graph limit theory in which such measures are viewed as limits of graph sequences.

Recommendations

• Flows on measurable spaces
• Random homomorphisms into the orthogonality graph
• Limits of dense graph sequences
• Measures on the square as sparse graph limits
• Limits of sequences of Markov chains

Cites work

• scientific article; zbMATH DE number 3721546 (Why is no real title available?)
• A generalization of Hölder's inequality and some probability inequalities
• Action convergence of operators and graphs
• An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Conditioning as disintegration
• Convergence of graphs with intermediate density
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Cut distance identifying graphon parameters over weak* limits
• Finitely forcible graphons
• Functional Analysis, Spectral Theory, and Applications
• Graph norms and Sidorenko's conjecture
• Identifiability for graphexes and the weak kernel metric
• Large networks and graph limits
• Measure theory. Vol. I and II
• Measures on the square as sparse graph limits
• Multigraph limits, unbounded kernels, and Banach space decorated graphs
• Sparse exchangeable graphs and their limits via graphon processes
• The step Sidorenko property and non-norming edge-transitive graphs

Cited in

(1)

• Random homomorphisms into the orthogonality graph

This page was built for publication: Subgraph densities in Markov spaces

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