Rooting algebraic vertices of convergent sequences

EUROCOMB’23

David Hartman Tomáš Hons Jaroslav Nešetřil

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

PDF
Abstract
Structural convergence is a framework for convergence of graphs by Nešetřil and Ossona de Mendez that unifies the dense (left) graph convergence and Benjamini-Schramm convergence. They posed a problem asking whether for a given sequence of graphs $(G_n)$ converging to a limit $L$ and a vertex $r$ of $L$ it is possible to find a sequence of vertices $(r_n)$ such that $L$ rooted at $r$ is the limit of the graphs $G_n$ rooted at $r_n$. A counterexample was found by Christofides and Král‘, but they showed that the statement holds for almost all vertices $r$ of $L$. We offer another perspective to the original problem by considering the size of definable sets to which the root $r$ belongs. We prove that if $r$ is an algebraic vertex (i.e. belongs to a finite definable set), the sequence of roots $(r_n)$ always exists.

Pages:
539–544
References

Benjamini, I., & Schramm, O. (2001). Recurrence of Distributional Limits of Finite Planar Graphs. Electronic Journal of Probability, 6(none). https://doi.org/10.1214/ejp.v6-96
https://doi.org/10.1214/EJP.v6-96

Borgs, C., Chayes, J., Lovász, L., Sós, V. T., & Vesztergombi, K. (2006). Counting Graph Homomorphisms. In Topics in Discrete Mathematics (pp. 315-371). Springer Berlin Heidelberg. https://doi.org/https://doi.org/10.1007/3-540-33700-8_18
https://doi.org/10.1007/3-540-33700-8_18

Christofides, D., & Král', D. (2015). First-Order Convergence and Roots. Combinatorics, Probability and Computing, 25(2), 213-221. https://doi.org/10.1017/s0963548315000048
https://doi.org/10.1017/S0963548315000048

Elek, G. (2007). Note on limits of finite graphs. Combinatorica, 27(4), 503-507. https://doi.org/10.1007/s00493-007-2214-8
https://doi.org/10.1007/s00493-007-2214-8

Hartman, D., Hons, T., & Nešetřil, J. (2022). Gadget construction and structural convergence. arXiv. https://doi.org/10.48550/ARXIV.2212.10985

Lovász, L. (2012). Large networks and graph limits. American Mathematical Society.
https://doi.org/10.1090/coll/060

Lovász, L., & Szegedy, B. (2006). Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6), 933-957. https://doi.org/10.1016/j.jctb.2006.05.002
https://doi.org/10.1016/j.jctb.2006.05.002

Nešetřil, J., & de Mendez, P. O. (2017). Cluster analysis of local convergent sequences of structures. Random Structures & Algorithms, 51(4), 674-728. https://doi.org/10.1002/rsa.20719
https://doi.org/10.1002/rsa.20719

Nešetřil, J., & de Mendez, P. O. (2019). Existence of Modeling Limits for Sequences of Sparse Structures. The Journal of Symbolic Logic, 84(2), 452-472. https://doi.org/10.1017/jsl.2018.32
https://doi.org/10.1017/jsl.2018.32

Nešetřil, J., & de Mendez, P. O. (2020). A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth. Memoirs of the American Mathematical Society, 263(1272). https://doi.org/10.1090/memo/1272
https://doi.org/10.1090/memo/1272

Stanley, R. P., & Fomin, S. (1999). Enumerative Combinatorics. Cambridge University Press. https://doi.org/10.1017/cbo9780511609589
https://doi.org/10.1017/CBO9780511609589

Whitney, H. (1972). Complex Analytic Varieties (p. 399). Addsion Weslsey Longman Publishing Group.

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 Hartman, Tomáš Hons, Jaroslav Nešetřil

PDF