A compactification of the set of sequences of positive real numbers with applications to limits of graphs

EUROCOMB’23

David Chodounsky Lluis Vena

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-038

PDF
Abstract
We introduce compactification results on the set of sequences of positive real numbers: under the continuum hypothesis, one can find a totally ordered set of sequences whose elements can be used as test sequences to capture every possible asympthotic growth, perhaps along a subsequence; this behaviour mimics the statement that, in a compact set of $\mathbb{R}$, every sequence has a convergent partial subsequence. These compactification results allows us to unify two notions of convergence for graphs into a single graph-convergence notion, while retaining the property that each sequence of graphs have a convergent partial subsequence. These convergent notions are the Benjamini-Schramm convergence for bounded degree graphs, regarding the distribution of r-neighbourhoods of the vertices, and the left-convergence for dense graphs, regarding the existence, for each fixed graph $F$, of a limiting probability that a random mapping from $F$ to $\{G_i\}$ is a graph homomorphism.

Pages:
277–282
References

Á. Backhausz and B. Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74(1):72-121, 2022.
https://doi.org/10.4153/S0008414X2000070X

I. Benjamini and O. Schramm. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab., 6:no. 23, 13 pp. (electronic), 2001.
https://doi.org/10.1214/EJP.v6-96

C. Borgs, J. Chayes, H. Cohn, and Y. Zhao. An Lp theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 372(5):3019-3062, 2019.
https://doi.org/10.1090/tran/7543

C. Borgs, J. Chayes, L. Lovász, V. T. Sós, B. Szegedy, and K. Vesztergombi. Graph limits and parameter testing. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 261-270, 2006.
https://doi.org/10.1145/1132516.1132556

C. Borgs, J. T. Chayes, H. Cohn, and Y. Zhao. An Lp theory of sparse graph convergence II: LD convergence, quotients and right convergence. The Annals of Probability, 46(1):337 - 396, 2018.
https://doi.org/10.1214/17-AOP1187

P. Frenkel. Convergence of graphs with intermediate density. Transactions of the American Mathematical Society, 370(5):3363-3404, 2018.
https://doi.org/10.1090/tran/7036

H. Hatami, L. Lovász, and B. Szegedy. Limits of locally-globally convergent graph sequences. Geometric and Functional Analysis, 24(1):269-296, 2014.
https://doi.org/10.1007/s00039-014-0258-7

C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, and R. Menezes Sampaio. Limits of permutation sequences. Journal of Combinatorial Theory, Series B, 103(1):93-113, 2013.
https://doi.org/10.1016/j.jctb.2012.09.003

L. Lovász. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.
https://doi.org/10.1090/coll/060

J. Nešetril and P. Ossona De Mendez. A model theory approach to structural limits. Commentationes Mathematicae Universitatis Carolinae, 53(4):581-603, 2012.

B. Szegedy. Sparse graph limits, entropy maximization and transitive graphs. arXiv preprint arXiv:1504.00858, 2015.

L. Vena. On limits of sparse random graphs. Electronic Notes in Discrete Mathematics, 54:343-348, 2016. Discrete Mathematics Days - JMDA16.
https://doi.org/10.1016/j.endm.2016.09.059

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 David Chodounsky, Lluis Vena

PDF