Local-global convergence, an analytic and structural approach

Jaroslav Nešetřil; Patrice Ossona de Mendez

Commentationes Mathematicae Universitatis Carolinae (2019)

  • Volume: 60, Issue: 1, page 97-129
  • ISSN: 0010-2628

Abstract

top
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.

How to cite

top

Nešetřil, Jaroslav, and Ossona de Mendez, Patrice. "Local-global convergence, an analytic and structural approach." Commentationes Mathematicae Universitatis Carolinae 60.1 (2019): 97-129. <http://eudml.org/doc/294297>.

@article{Nešetřil2019,
abstract = {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.},
author = {Nešetřil, Jaroslav, Ossona de Mendez, Patrice},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {structural limit; Borel structure; modeling; local-global convergence},
language = {eng},
number = {1},
pages = {97-129},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Local-global convergence, an analytic and structural approach},
url = {http://eudml.org/doc/294297},
volume = {60},
year = {2019},
}

TY - JOUR
AU - Nešetřil, Jaroslav
AU - Ossona de Mendez, Patrice
TI - Local-global convergence, an analytic and structural approach
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2019
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 60
IS - 1
SP - 97
EP - 129
AB - 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.
LA - eng
KW - structural limit; Borel structure; modeling; local-global convergence
UR - http://eudml.org/doc/294297
ER -

References

top
  1. Adler H., Adler I., 10.1016/j.ejc.2013.06.048, European J. Combin. 36 (2014), 322–330. MR3131898DOI10.1016/j.ejc.2013.06.048
  2. Aldous D. J., 10.1016/0047-259X(81)90099-3, J. Multivariate Anal. 11 (1981), no. 4, 581–598. MR0637937DOI10.1016/0047-259X(81)90099-3
  3. Alon N., 10.1007/BF02579166, Theory of computing, Combinatorica 6 (1986), no. 2, 83–96. MR0875835DOI10.1007/BF02579166
  4. Balcar B., Jech T., Pazák T., 10.1112/S0024609305004807, Bull. London Math. Soc. 37 (2005), no. 6, 885–898. MR2186722DOI10.1112/S0024609305004807
  5. Benjamini I., Schramm O., 10.1214/EJP.v6-96, Electron. J. Probab. 6 (2001), no. 23, 13 pages. MR1873300DOI10.1214/EJP.v6-96
  6. Bollobás B., Riordan O., 10.1002/rsa.20334, Random Structures Algorithms 39 (2011), no. 1, 1–38. MR2839983DOI10.1002/rsa.20334
  7. Borgs Ch., Chayes J., Lovász L., 10.1007/s00039-010-0044-0, Geom. Funct. Anal. 19 (2010), no. 6, 1597–1619. MR2594615DOI10.1007/s00039-010-0044-0
  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. MR2277152
  9. Borgs C., Chayes J. T., Lovász L., Sós V. T., Vesztergombi K., 10.1016/j.aim.2008.07.008, Adv. Math. 219 (2008), no. 6, 1801–1851. MR2455626DOI10.1016/j.aim.2008.07.008
  10. Borgs C., Chayes J. T., Lovász L., Sós V. T., Vesztergombi K., 10.4007/annals.2012.176.1.2, Ann. of Math. (2) 176 (2012), no. 1, 151–219. MR2925382DOI10.4007/annals.2012.176.1.2
  11. Gajarský J., Hliněný P., Kaiser T., Král' D., Kupec M., Obdržálek J., Ordyniak S., Tůma V., 10.1002/rsa.20676, Random Structures Algorithms 50 (2017), no. 4, 612–635. MR3660522DOI10.1002/rsa.20676
  12. Hatami H., Lovász L., Szegedy B., 10.1007/s00039-014-0258-7, Geom. Funct. Anal. 24 (2014), no. 1, 269–296. MR3177383DOI10.1007/s00039-014-0258-7
  13. Hausdorff F., Set Theory, Chelsea Publishing, New York, 1962. MR0141601
  14. Hodges W., A Shorter Model Theory, Cambridge University Press, Cambridge, 1997. Zbl0873.03036MR1462612
  15. Hoory S., Linial N., Wigderson A., 10.1090/S0273-0979-06-01126-8, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR2247919DOI10.1090/S0273-0979-06-01126-8
  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). Zbl1205.00006MR3408502
  19. Lovász L., Szegedy B., 10.1016/j.jctb.2006.05.002, J. Comb. Theory Ser. B 96 (2006), no. 6, 933–957. Zbl1113.05092MR2274085DOI10.1016/j.jctb.2006.05.002
  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. MR3016428
  21. Nešetřil J., Ossona de Mendez P., 10.1016/j.ejc.2015.07.012, European J. Combin. 52 (2016), part B, 368–388. MR3425985DOI10.1016/j.ejc.2015.07.012
  22. Nešetřil J., Ossona de Mendez P., 10.37236/5628, Electron. J. Combin. 23 (2016), no. 2, paper 2.52, 33 pages. MR3522136DOI10.37236/5628
  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. MR3507464
  24. Nešetřil J., Ossona de Mendez P., 10.1002/rsa.20719, Random Structures Algorithms 51 (2017), no. 4, 674–728. MR3718594DOI10.1002/rsa.20719
  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. MR2226435
  26. Nešetřil J., Ossona de Mendez P., 10.1017/jsl.2018.32, published online in J. Symb. Log. (2019), 22 pages. doi:10.1017/jsl.2018.32. DOI10.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). MR0049131

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.