Subgraph densities in Markov spaces

DOI10.1016/J.AIM.2023.109414arXiv2206.04493MaRDI QIDQ6184559FDOQ6184559

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)

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.

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

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

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)

Cites Work

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

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)