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

EUROCOMB’23

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