| Title:
|
A model theory approach to structural limits (English) |
| Author:
|
Nešetřil, Jaroslav |
| Author:
|
Mendez, Patrice Ossona de |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
53 |
| Issue:
|
4 |
| Year:
|
2012 |
| Pages:
|
581-603 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph |
| Keyword:
|
graph limits |
| Keyword:
|
model theory |
| Keyword:
|
first-order logic |
| MSC:
|
05C99 |
| idMR:
|
MR3016428 |
| . |
| Date available:
|
2013-03-02T13:45:35Z |
| Last updated:
|
2015-02-11 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143192 |
| . |
| Reference:
|
[1] Adams S.: Trees and amenable equivalence relations.Ergodic Theory Dynam. Systems 10 (1990), 1–14. Zbl 0667.28003, MR 1053796 |
| Reference:
|
[2] Aldous D., Lyons R.: Processes on unimodular random networks.arXiv:math/0603062 (2006). Zbl 1131.60003, MR 2354165 |
| Reference:
|
[3] Benjamini I., Schramm O.: Recurrence of distibutional limits of finite planar graphs.Electron. J. Probab. 6 (2001), no. 23, 13pp. MR 1873300, 10.1214/EJP.v6-96 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[6] Elek G.: Note on limits of finite graphs.Combinatorica 27 (2007), 503–507, DOI 10.1007/s00493-007-2214-8. MR 2359831, 10.1007/s00493-007-2214-8 |
| Reference:
|
[7] Elek G., Szegedy B.: Limits of hypergraphs, removal and regularity lemmas. A non-standard approach.arXiv:0705.2179v1 [math.CO] (2007). |
| Reference:
|
[8] Gaboriau D.: Invariant percolation and harmonic Dirichlet functions.Geom. Funct. Anal. 15 (2005), 1004–1051, DOI 10.1007/s00039-005-0539-2. Zbl 1099.60070, MR 2221157, 10.1007/s00039-005-0539-2 |
| Reference:
|
[9] Gaifman H.: On local and non-local properties.in Proceedings of the Herbrand Symposium, Logic Colloquium '81, 1982. Zbl 0518.03008 |
| Reference:
|
[10] Halmos P., Givant S.: Logic as Algebra.Dolciani Mathematical Expositions, 21, The Mathematical Association of America, Washington DC, 1998. Zbl 1053.03001, MR 1612588 |
| Reference:
|
[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. Zbl 0166.25801, MR 0210570 |
| Reference:
|
[12] Hodges W.: A Shorter Model Theory.Cambridge University Press, Cambridge, 1997. Zbl 0873.03036, MR 1462612 |
| Reference:
|
[13] Lascar D.: La théorie des modèles en peu de maux.Cassini, 2009. Zbl 1205.00006 |
| Reference:
|
[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. Zbl 0068.24401 |
| Reference:
|
[15] Lovász L., Szegedy B.: Limits of dense graph sequences.J. Combin. Theory Ser. B 96 (2006), 933–957. Zbl 1113.05092, MR 2274085, 10.1016/j.jctb.2006.05.002 |
| Reference:
|
[16] Martin D., Steel J.: A proof of projective determinacy.J. Amer. Math. Soc. 2 (1989), no. 1, 71–125. Zbl 0668.03021, MR 0955605, 10.1090/S0894-0347-1989-0955605-X |
| Reference:
|
[17] Matoušek J., Nešetřil J.: Invitation to Discrete Mathematics.Oxford University Press, New York, 1998 (second edition 2009). Zbl 1152.05002, MR 2469243 |
| Reference:
|
[18] Mycielski J., Świerczkowski S.: On the Lebesgue measurability and the axiom of determinateness.Fund. Math. 54 (1964), 67–71. Zbl 0147.19503, MR 0161788 |
| Reference:
|
[19] Nešetřil J., Ossona de Mendez P.: Tree depth, subgraph coloring and homomorphism bounds.European J. Combin. 27 (2006), no. 6, 1022–1041, DOI 10.1016/j.ejc.2005.01.010. MR 2226435, 10.1016/j.ejc.2005.01.010 |
| Reference:
|
[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. MR 2648324 |
| Reference:
|
[21] Nešetřil J., Ossona de Mendez P.: Sparsity. Graphs, Structures, and Algorithms.Algorithms and Combinatorics, 28, Springer, Heidelberg, 2012, 465 pp. MR 2920058, 10.1007/978-3-642-27875-4 |
| Reference:
|
[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. |
| Reference:
|
[23] Rudin W.: Functional Analysis.Mc-Graw Hill, New York, 1973. Zbl 0867.46001, MR 0365062 |
| Reference:
|
[24] Stone M.: The theory of representations of Boolean algebras.Trans. Amer. Math. Soc. 40 (1936), 37–111. MR 1501865 |
| . |
