Subgraph densities in Markov spaces. (English) Zbl 1531.05179
Summary: 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.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 60F05 | Central limit and other weak theorems |
| 60C05 | Combinatorial probability |
References:
| [1] | Backhausz, Á.; Szegedy, B., Action convergence of operators and graphs. Can. J. Math., 72-121 (2022) · Zbl 1482.05187 |
| [2] | Bogachev, V. I.; Ruas, M. A.S., Measure Theory, Volume II (2007), Springer · Zbl 1120.28001 |
| [3] | Borgs, C.; Chayes, J.; Cohn, H.; Holden, N., Sparse exchangeable graphs and their limits via graphon processes. J. Mach. Learn. Res. (2018), 71 pp. · Zbl 1469.60158 |
| [4] | Borgs, C.; Chayes, J.; Cohn, H.; Lovász, L. M., Identifiability for graphexes and the weak kernel metric, 29-157 · Zbl 1443.05169 |
| [5] | Borgs, C.; Chayes, J.; Cohn, H.; Zhao, Y., An \(L^p\) theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. Trans. Am. Math. Soc., 3019-3062 (2019) · Zbl 1417.05186 |
| [6] | Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Convergent graph sequences II: multiway cuts and statistical physics. Ann. Math., 151-219 (2012) · Zbl 1247.05124 |
| [7] | Chang, J. T.; Pollard, D., Conditioning as disintegration. Stat. Neerl., 287-317 (1997) · Zbl 0889.62003 |
| [8] | Doležal, M.; Grebík, J.; Hladký, J.; Rocha, I.; Rozhoň, V., Cut distance identifying graphon parameters over weak* limits. J. Comb. Theory, Ser. A (July 2022) · Zbl 1486.05276 |
| [9] | Einsiedler, M.; Ward, T., Functional Analysis, Spectral Theory, and Applications. Graduate Texts in Mathematics (2017), Springer · Zbl 1387.46001 |
| [10] | Finner, H., A generalization of Hölder’s inequality and some probability inequalities. Ann. Probab., 1893-1901 (1992) · Zbl 0761.60013 |
| [11] | Frenkel, P., Convergence of graphs with intermediate density. Trans. Am. Math. Soc., 3363-3404 (2018) · Zbl 1380.05061 |
| [12] | Glim, J.; Jaffe, A., Quantum Physics, a Functional Integral Point of View (1981), Springer-Verlag · Zbl 0461.46051 |
| [13] | Hatami, H., Graph norms and Sidorenko’s conjecture. Isr. J. Math., 125-150 (2010) · Zbl 1227.05183 |
| [14] | Král’, D.; Martins, T.; Pach, P. P.; Wrochna, M., The step Sidorenko property and non-norming edge-transitive graphs. J. Comb. Theory, Ser. A, 34-54 (2019) · Zbl 1401.05269 |
| [15] | Kunszenti-Kovács, D.; Lovász, L.; Szegedy, B., Multigraph limits, unbounded kernels, and Banach space decorated graphs. J. Funct. Anal., 2 (2022) · Zbl 1479.05342 |
| [16] | Kunszenti-Kovács, D.; Lovász, L.; Szegedy, B., Measures on the square as sparse graph limits. J. Comb. Theory, Ser. B, 1-40 (2019) · Zbl 1415.05099 |
| [17] | Kunszenti-Kovács, D.; Lovász, L.; Szegedy, B., Random homomorphisms into the orthogonality graph · Zbl 1536.05329 |
| [18] | Lovász, L., Large Networks and Graph Limits (2012), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI · Zbl 1292.05001 |
| [19] | Lovász, L.; Szegedy, B., The graph theoretic moment problem |
| [20] | Lovász, L.; Szegedy, B., Finitely forcible graphons. J. Comb. Theory, Ser. B, 269-301 (2011) · Zbl 1223.05248 |
| [21] | Veitch, V.; Roy, D. M., The class of random graphs arising from exchangeable random measures |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
