| Title:
|
Local-global convergence, an analytic and structural approach (English) |
| Author:
|
Nešetřil, Jaroslav |
| Author:
|
Ossona de Mendez, Patrice |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
60 |
| Issue:
|
1 |
| Year:
|
2019 |
| Pages:
|
97-129 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
structural limit |
| Keyword:
|
Borel structure |
| Keyword:
|
modeling |
| Keyword:
|
local-global convergence |
| MSC:
|
03C13 |
| MSC:
|
03C98 |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 07088827 |
| idMR:
|
MR3946666 |
| DOI:
|
10.14712/1213-7243.2015.280 |
| . |
| Date available:
|
2019-05-13T07:49:25Z |
| Last updated:
|
2021-04-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147669 |
| . |
| Reference:
|
[1] Adler H., Adler I.: Interpreting nowhere dense graph classes as a classical notion of model theory.European J. Combin. 36 (2014), 322–330. MR 3131898, 10.1016/j.ejc.2013.06.048 |
| Reference:
|
[2] Aldous D. J.: Representations for partially exchangeable arrays of random variables.J. Multivariate Anal. 11 (1981), no. 4, 581–598. MR 0637937, 10.1016/0047-259X(81)90099-3 |
| Reference:
|
[3] Alon N.: Eigenvalues and expanders.Theory of computing, Combinatorica 6 (1986), no. 2, 83–96. MR 0875835, 10.1007/BF02579166 |
| Reference:
|
[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. MR 2186722, 10.1112/S0024609305004807 |
| Reference:
|
[5] Benjamini I., Schramm O.: Recurrence of distributional limits of finite planar graphs.Electron. J. Probab. 6 (2001), no. 23, 13 pages. MR 1873300, 10.1214/EJP.v6-96 |
| Reference:
|
[6] Bollobás B., Riordan O.: Sparse graphs: metrics and random models.Random Structures Algorithms 39 (2011), no. 1, 1–38. MR 2839983, 10.1002/rsa.20334 |
| Reference:
|
[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. MR 2594615, 10.1007/s00039-010-0044-0 |
| Reference:
|
[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 |
| Reference:
|
[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. MR 2455626, 10.1016/j.aim.2008.07.008 |
| Reference:
|
[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. MR 2925382, 10.4007/annals.2012.176.1.2 |
| Reference:
|
[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. MR 3660522, 10.1002/rsa.20676 |
| Reference:
|
[12] Hatami H., Lovász L., Szegedy B.: Limits of locally-globally convergent graph sequences.Geom. Funct. Anal. 24 (2014), no. 1, 269–296. MR 3177383, 10.1007/s00039-014-0258-7 |
| Reference:
|
[13] Hausdorff F.: Set Theory.Chelsea Publishing, New York, 1962. MR 0141601 |
| Reference:
|
[14] Hodges W.: A Shorter Model Theory.Cambridge University Press, Cambridge, 1997. Zbl 0873.03036, MR 1462612 |
| Reference:
|
[15] Hoory S., Linial N., Wigderson A.: Expander graphs and their applications.Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, 10.1090/S0273-0979-06-01126-8 |
| Reference:
|
[16] Hoover D.: Relations on Probability Spaces and arrays of Random Variables.Tech. report, Institute for Advanced Study, Princeton, 1979. |
| Reference:
|
[17] Kun G., Thom A.: Inapproximability of actions and Kazhdan's property (T).available at arXiv:1901.03963 [math.GR] (2019), 9 pages. |
| Reference:
|
[18] Lascar D.: La théorie des modèles en peu de maux.Nouvelle Bibliothèque Mathématique, 10, Cassini, Paris, 2009 (French). Zbl 1205.00006, MR 3408502 |
| Reference:
|
[19] Lovász L., Szegedy B.: Limits of dense graph sequences.J. Comb. Theory Ser. B 96 (2006), no. 6, 933–957. Zbl 1113.05092, MR 2274085, 10.1016/j.jctb.2006.05.002 |
| Reference:
|
[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 |
| Reference:
|
[21] Nešetřil J., Ossona de Mendez P.: First-order limits, an analytical perspective.European J. Combin. 52 (2016), part B, 368–388. MR 3425985, 10.1016/j.ejc.2015.07.012 |
| Reference:
|
[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. MR 3522136, 10.37236/5628 |
| Reference:
|
[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 |
| Reference:
|
[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. MR 3718594, 10.1002/rsa.20719 |
| Reference:
|
[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 |
| Reference:
|
[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. 10.1017/jsl.2018.32 |
| Reference:
|
[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 |
| . |
