Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
structural limit; Borel structure; modeling; local-global convergence
structural limit; Borel structure; modeling; local-global convergence
Summary:
Based on methods of structural convergence we provide a unifying view of local-global convergence, fitting to model theory and analysis. The general approach outlined here provides a possibility to extend the theory of local-global convergence to graphs with unbounded degrees. As an application, we extend previous results on continuous clustering of local convergent sequences and prove the existence of modeling quasi-limits for local-global convergent sequences of nowhere dense graphs.
References:
[1] Adler H., Adler I.: Interpreting nowhere dense graph classes as a classical notion of model theory. European J. Combin. 36 (2014), 322–330. DOI 10.1016/j.ejc.2013.06.048 | MR 3131898
[2] Aldous D. J.: Representations for partially exchangeable arrays of random variables. J. Multivariate Anal. 11 (1981), no. 4, 581–598. DOI 10.1016/0047-259X(81)90099-3 | MR 0637937
[3] Alon N.: Eigenvalues and expanders. Theory of computing, Combinatorica 6 (1986), no. 2, 83–96. DOI 10.1007/BF02579166 | MR 0875835
[4] Balcar B., Jech T., Pazák T.: Complete CCC Boolean algebras, the order sequential topology, and a problem of von Neumann. Bull. London Math. Soc. 37 (2005), no. 6, 885–898. DOI 10.1112/S0024609305004807 | MR 2186722
[5] Benjamini I., Schramm O.: Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13 pages. DOI 10.1214/EJP.v6-96 | MR 1873300
[6] Bollobás B., Riordan O.: Sparse graphs: metrics and random models. Random Structures Algorithms 39 (2011), no. 1, 1–38. DOI 10.1002/rsa.20334 | MR 2839983
[7] Borgs Ch., Chayes J., Lovász L.: Moments of two-variable functions and the uniqueness of graph limits. Geom. Funct. Anal. 19 (2010), no. 6, 1597–1619. DOI 10.1007/s00039-010-0044-0 | MR 2594615
[8] Borgs Ch., Chayes J., Lovász L., Sós V. T., Szegedy B., Vesztergombi K.: Graph limits and parameter testing. STOC'06, Proc. of the 38th Annual ACM Symposium on Theory of Computing, 2006, pages 261–270. MR 2277152
[9] Borgs C., Chayes J. T., Lovász L., Sós V. T., Vesztergombi K.: Convergent sequences of dense graphs I. Subgraph frequencies, metric properties and testing. Adv. Math. 219 (2008), no. 6, 1801–1851. DOI 10.1016/j.aim.2008.07.008 | MR 2455626
[10] Borgs C., Chayes J. T., Lovász L., Sós V. T., Vesztergombi K.: Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Ann. of Math. (2) 176 (2012), no. 1, 151–219. DOI 10.4007/annals.2012.176.1.2 | MR 2925382
[11] Gajarský J., Hliněný P., Kaiser T., Král' D., Kupec M., Obdržálek J., Ordyniak S., Tůma V.: First order limits of sparse graphs: plane trees and path-width. Random Structures Algorithms 50 (2017), no. 4, 612–635. DOI 10.1002/rsa.20676 | MR 3660522
[12] Hatami H., Lovász L., Szegedy B.: Limits of locally-globally convergent graph sequences. Geom. Funct. Anal. 24 (2014), no. 1, 269–296. DOI 10.1007/s00039-014-0258-7 | MR 3177383
[13] Hausdorff F.: Set Theory. Chelsea Publishing, New York, 1962. MR 0141601
[14] Hodges W.: A Shorter Model Theory. Cambridge University Press, Cambridge, 1997. MR 1462612 | Zbl 0873.03036
[15] Hoory S., Linial N., Wigderson A.: Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. DOI 10.1090/S0273-0979-06-01126-8 | MR 2247919
[16] Hoover D.: Relations on Probability Spaces and arrays of Random Variables. Tech. report, Institute for Advanced Study, Princeton, 1979.
[17] Kun G., Thom A.: Inapproximability of actions and Kazhdan's property (T). available at arXiv:1901.03963 [math.GR] (2019), 9 pages.
[18] Lascar D.: La théorie des modèles en peu de maux. Nouvelle Bibliothèque Mathématique, 10, Cassini, Paris, 2009 (French). MR 3408502 | Zbl 1205.00006
[19] Lovász L., Szegedy B.: Limits of dense graph sequences. J. Comb. Theory Ser. B 96 (2006), no. 6, 933–957. DOI 10.1016/j.jctb.2006.05.002 | MR 2274085 | Zbl 1113.05092
[20] Nešetřil J., Ossona de Mendez P.: A model theory approach to structural limits. Comment. Math. Univ. Carolin. 53 (2012), no. 4, 581–603. MR 3016428
[21] Nešetřil J., Ossona de Mendez P.: First-order limits, an analytical perspective. European J. Combin. 52 (2016), part B, 368–388. DOI 10.1016/j.ejc.2015.07.012 | MR 3425985
[22] Nešetřil J., Ossona de Mendez P.: Modeling limits in hereditary classes: reduction and application to trees. Electron. J. Combin. 23 (2016), no. 2, paper 2.52, 33 pages. DOI 10.37236/5628 | MR 3522136
[23] Nešetřil J., Ossona de Mendez P.: Structural sparsity. Uspekhi Mat. Nauk 71 (2016), no. 1(427), 85–116; translation in Russian Math. Surveys 71 (2016), no. 1, 79–107. MR 3507464
[24] Nešetřil J., Ossona de Mendez P.: Cluster analysis of local convergent sequences of structures. Random Structures Algorithms 51 (2017), no. 4, 674–728. DOI 10.1002/rsa.20719 | MR 3718594
[25] Nešetřil J., Ossona de Mendez P.: A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth). to appear in Mem. Amer. Math. Soc. (2017), 117 pages. MR 2226435
[26] Nešetřil J., Ossona de Mendez P.: Existence of modeling limits for sequences of sparse structures. published online in J. Symb. Log. (2019), 22 pages. doi:10.1017/jsl.2018.32. DOI 10.1017/jsl.2018.32
[27] Urysohn P.: Works on Topology and Other Areas of Mathematics 1, 2. State Publ. of Technical and Theoretical Literature, Moskva, 1951, (Russian). MR 0049131
Search
Partner of
