Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graph; graph limits; model theory; first-order logic
graph; graph limits; model theory; first-order logic
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.
References:
[1] Adams S.: Trees and amenable equivalence relations. Ergodic Theory Dynam. Systems 10 (1990), 1–14. MR 1053796 | Zbl 0667.28003
[2] Aldous D., Lyons R.: Processes on unimodular random networks. arXiv:math/0603062 (2006). MR 2354165 | Zbl 1131.60003
[3] Benjamini I., Schramm O.: Recurrence of distibutional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13pp. DOI 10.1214/EJP.v6-96 | MR 1873300
[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.: Note on limits of finite graphs. Combinatorica 27 (2007), 503–507, DOI 10.1007/s00493-007-2214-8. DOI 10.1007/s00493-007-2214-8 | MR 2359831
[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.: Invariant percolation and harmonic Dirichlet functions. Geom. Funct. Anal. 15 (2005), 1004–1051, DOI 10.1007/s00039-005-0539-2. DOI 10.1007/s00039-005-0539-2 | MR 2221157 | Zbl 1099.60070
[9] Gaifman H.: On local and non-local properties. in Proceedings of the Herbrand Symposium, Logic Colloquium '81, 1982. Zbl 0518.03008
[10] Halmos P., Givant S.: Logic as Algebra. Dolciani Mathematical Expositions, 21, The Mathematical Association of America, Washington DC, 1998. MR 1612588 | Zbl 1053.03001
[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. MR 0210570 | Zbl 0166.25801
[12] Hodges W.: A Shorter Model Theory. Cambridge University Press, Cambridge, 1997. MR 1462612 | Zbl 0873.03036
[13] Lascar D.: La théorie des modèles en peu de maux. Cassini, 2009. Zbl 1205.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. Zbl 0068.24401
[15] Lovász L., Szegedy B.: Limits of dense graph sequences. J. Combin. Theory Ser. B 96 (2006), 933–957. DOI 10.1016/j.jctb.2006.05.002 | MR 2274085 | Zbl 1113.05092
[16] Martin D., Steel J.: A proof of projective determinacy. J. Amer. Math. Soc. 2 (1989), no. 1, 71–125. DOI 10.1090/S0894-0347-1989-0955605-X | MR 0955605 | Zbl 0668.03021
[17] Matoušek J., Nešetřil J.: Invitation to Discrete Mathematics. Oxford University Press, New York, 1998 (second edition 2009). MR 2469243 | Zbl 1152.05002
[18] Mycielski J., Świerczkowski S.: On the Lebesgue measurability and the axiom of determinateness. Fund. Math. 54 (1964), 67–71. MR 0161788 | Zbl 0147.19503
[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. DOI 10.1016/j.ejc.2005.01.010 | MR 2226435
[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
[21] Nešetřil J., Ossona de Mendez P.: Sparsity. Graphs, Structures, and Algorithms. Algorithms and Combinatorics, 28, Springer, Heidelberg, 2012, 465 pp. DOI 10.1007/978-3-642-27875-4 | MR 2920058
[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. MR 0365062 | Zbl 0867.46001
[24] Stone M.: The theory of representations of Boolean algebras. Trans. Amer. Math. Soc. 40 (1936), 37–111. MR 1501865
Search
Partner of
