A model theory approach to structural limits

Jaroslav Nešetřil; Patrice Ossona de Mendez

Commentationes Mathematicae Universitatis Carolinae (2012)

  • Volume: 53, Issue: 4, page 581-603
  • ISSN: 0010-2628

Abstract

top
The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a combination of model theory and analysis. Then, as an example, we generalize limits of bounded degree graphs from subgraph testing to finite model testing.

How to cite

top

Nešetřil, Jaroslav, and Mendez, Patrice Ossona de. "A model theory approach to structural limits." Commentationes Mathematicae Universitatis Carolinae 53.4 (2012): 581-603. <http://eudml.org/doc/252546>.

@article{Nešetřil2012,
abstract = {The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a combination of model theory and analysis. Then, as an example, we generalize limits of bounded degree graphs from subgraph testing to finite model testing.},
author = {Nešetřil, Jaroslav, Mendez, Patrice Ossona de},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph; graph limits; model theory; first-order logic; graph limits; model theory; first-order logic},
language = {eng},
number = {4},
pages = {581-603},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {A model theory approach to structural limits},
url = {http://eudml.org/doc/252546},
volume = {53},
year = {2012},
}

TY - JOUR
AU - Nešetřil, Jaroslav
AU - Mendez, Patrice Ossona de
TI - A model theory approach to structural limits
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2012
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 53
IS - 4
SP - 581
EP - 603
AB - The goal of this paper is to unify two lines in a particular area of graph limits. First, we generalize and provide unified treatment of various graph limit concepts by means of a combination of model theory and analysis. Then, as an example, we generalize limits of bounded degree graphs from subgraph testing to finite model testing.
LA - eng
KW - graph; graph limits; model theory; first-order logic; graph limits; model theory; first-order logic
UR - http://eudml.org/doc/252546
ER -

References

top
  1. Adams S., Trees and amenable equivalence relations, Ergodic Theory Dynam. Systems 10 (1990), 1–14. Zbl0667.28003MR1053796
  2. Aldous D., Lyons R., Processes on unimodular random networks, arXiv:math/0603062 (2006). Zbl1131.60003MR2354165
  3. Benjamini I., Schramm O., 10.1214/EJP.v6-96, Electron. J. Probab. 6 (2001), no. 23, 13pp. MR1873300DOI10.1214/EJP.v6-96
  4. Borgs C., Chayes J., Lovász L., Sós V., Szegedy B., Vesztergombi K., Graph limits and parameter testing, in Proc. 38th Annual {ACM} Symp. Principles of Dist. Comp., pp. 51–59, 2005. 
  5. Conley C., Kechris A., Tucker-Drob R., Ultraproducts of measure preserving actions and graph combinatorics, Ergodic Theory and Dynamical Systems (2012), DOI 10.1017/S0143385711001143. 
  6. Elek G., 10.1007/s00493-007-2214-8, Combinatorica 27 (2007), 503–507, DOI 10.1007/s00493-007-2214-8. MR2359831DOI10.1007/s00493-007-2214-8
  7. Elek G., Szegedy B., Limits of hypergraphs, removal and regularity lemmas. A non-standard approach, arXiv:0705.2179v1 [math.CO] (2007). 
  8. Gaboriau D., 10.1007/s00039-005-0539-2, Geom. Funct. Anal. 15 (2005), 1004–1051, DOI 10.1007/s00039-005-0539-2. Zbl1099.60070MR2221157DOI10.1007/s00039-005-0539-2
  9. Gaifman H., On local and non-local properties, in Proceedings of the Herbrand Symposium, Logic Colloquium '81, 1982. Zbl0518.03008
  10. Halmos P., Givant S., Logic as Algebra, Dolciani Mathematical Expositions, 21, The Mathematical Association of America, Washington DC, 1998. Zbl1053.03001MR1612588
  11. Hanf W., Model-theoretic methods in the study of elementary logic, in Theory of Models, J. Addison, L. Henkin, A. Tarski (eds.), pp. 132–145, North-Holland, Amsterdam, 1965. Zbl0166.25801MR0210570
  12. Hodges W., A Shorter Model Theory, Cambridge University Press, Cambridge, 1997. Zbl0873.03036MR1462612
  13. Lascar D., La théorie des modèles en peu de maux, Cassini, 2009. Zbl1205.00006
  14. Łoś J., Quelques remarques, théorèmes et problèmes sur les classes définissables d'algèbres, in Mathematical Interpretation of Formal Systems, Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1955. Zbl0068.24401
  15. Lovász L., Szegedy B., 10.1016/j.jctb.2006.05.002, J. Combin. Theory Ser. B 96 (2006), 933–957. Zbl1113.05092MR2274085DOI10.1016/j.jctb.2006.05.002
  16. Martin D., Steel J., 10.1090/S0894-0347-1989-0955605-X, J. Amer. Math. Soc. 2 (1989), no. 1, 71–125. Zbl0668.03021MR0955605DOI10.1090/S0894-0347-1989-0955605-X
  17. Matoušek J., Nešetřil J., Invitation to Discrete Mathematics, Oxford University Press, New York, 1998 (second edition 2009). Zbl1152.05002MR2469243
  18. Mycielski J., Świerczkowski S., On the Lebesgue measurability and the axiom of determinateness, Fund. Math. 54 (1964), 67–71. Zbl0147.19503MR0161788
  19. Nešetřil J., Ossona de Mendez P., 10.1016/j.ejc.2005.01.010, European J. Combin. 27 (2006), no. 6, 1022–1041, DOI 10.1016/j.ejc.2005.01.010. MR2226435DOI10.1016/j.ejc.2005.01.010
  20. Nešetřil J., Ossona de Mendez P., From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits, in European Congress of Mathematics, pp. 135–165, European Mathematical Society, Zürich, 2010, DOI 10.4171/077-1/7. MR2648324
  21. Nešetřil J., Ossona de Mendez P., 10.1007/978-3-642-27875-4, Algorithms and Combinatorics, 28, Springer, Heidelberg, 2012, 465 pp. MR2920058DOI10.1007/978-3-642-27875-4
  22. Nešetřil J., Ossona de Mendez P., Graph limits: a unified approach with application to the study of limits of graphs with bounded diameter components, manuscript, 2012. 
  23. Rudin W., Functional Analysis, Mc-Graw Hill, New York, 1973. Zbl0867.46001MR0365062
  24. Stone M., The theory of representations of Boolean algebras, Trans. Amer. Math. Soc. 40 (1936), 37–111. MR1501865

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.