Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing.(English)Zbl 1213.05161
Summary: We consider sequences of graphs \((G_n)\) and define various notions of convergence related to these sequences: “left convergence” defined in terms of the densities of homomorphisms from small graphs into \(G_n\); “right convergence” defined in terms of the densities of homomorphisms from \(Gn\) into small graphs; and convergence in a suitably defined metric.
In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs \(G_n\), and for graphs \(G_n\) with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural formulations of Szemerédi partitions, sampling and testing of large graphs.
In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs \(G_n\), and for graphs \(G_n\) with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural formulations of Szemerédi partitions, sampling and testing of large graphs.
MSC:
| 05C42 | Density (toughness, etc.) |
Keywords:
graph sequences;cut metric;sampling;parameter testing;Szemerédi partitions;partition functions;free energiesCite
References:
| [1] | N. Alon, W. Fernandez de la Vega, R. Kannan, M. Karpinski, Random sampling and approximation of MAX-CSP problems, in: Proc. of the 34th ACM Symp. Theor. of Comp. (STOC), 2002, pp. 232-239; N. Alon, W. Fernandez de la Vega, R. Kannan, M. Karpinski, Random sampling and approximation of MAX-CSP problems, in: Proc. of the 34th ACM Symp. Theor. of Comp. (STOC), 2002, pp. 232-239 ·Zbl 1192.68865 |
| [2] | Alon, N.; Fernandez de la Vega, W.; Kannan, R.; Karpinski, M., Random sampling and approximation of MAX-CSPs, J. Comput. System Sci., 67, 212-243 (2003) ·Zbl 1160.68537 |
| [3] | Alon, N.; Fisher, E.; Krivelevich, M.; Szegedy, M., Efficient testing of large graphs, Combinatorica, 20, 451-476 (2000) ·Zbl 1052.68096 |
| [4] | N. Alon, E. Fischer, I. Newman, A. Shapira, A combinatorial characterization of the testable graph properties: It’s all about regularity, in: Proc. of the 38th ACM Symp. Theor. of Comp. (STOC), 2006, pp. 251-260; N. Alon, E. Fischer, I. Newman, A. Shapira, A combinatorial characterization of the testable graph properties: It’s all about regularity, in: Proc. of the 38th ACM Symp. Theor. of Comp. (STOC), 2006, pp. 251-260 ·Zbl 1301.05354 |
| [5] | Alon, N.; Naor, A., Approximating the cut-norm via Grothendieck’s inequality, (Proc. of the 36 ACM STOC (2004), ACM Press: ACM Press Chicago). (Proc. of the 36 ACM STOC (2004), ACM Press: ACM Press Chicago), SIAM J. Comput., 35, 787-803 (2006), journal version: ·Zbl 1096.68163 |
| [6] | N. Alon, A. Shapira, Every monotone graph property is testable, in: Proc. of the 37th ACM Symp. Theor. of Comp. (STOC), 2005, pp. 128-137; N. Alon, A. Shapira, Every monotone graph property is testable, in: Proc. of the 37th ACM Symp. Theor. of Comp. (STOC), 2005, pp. 128-137 ·Zbl 1192.68466 |
| [7] | Barabasi, A.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) ·Zbl 1226.05223 |
| [8] | Benjamini, I.; Schramm, O., Recurrence of distributional limits of finite planar graphs, Electron. J. Probab., 6, 23, 1-13 (2001) ·Zbl 1010.82021 |
| [9] | N. Berger, C. Borgs, J.T. Chayes, A. Saberi, On the spread of viruses on the Internet, in: Proc. of the 16th ACM-SIAM Symp. on Discr. Alg. (SODA), 2005, pp. 301-310; N. Berger, C. Borgs, J.T. Chayes, A. Saberi, On the spread of viruses on the Internet, in: Proc. of the 16th ACM-SIAM Symp. on Discr. Alg. (SODA), 2005, pp. 301-310 ·Zbl 1297.68029 |
| [10] | B. Bollobas, C. Borgs, J.T. Chayes, O. Riordan, Directed scale-free graphs, in: Proc of the 14th ACM-SIAM Symp. on Discr. Alg. (SODA), 2003, pp. 132-139; B. Bollobas, C. Borgs, J.T. Chayes, O. Riordan, Directed scale-free graphs, in: Proc of the 14th ACM-SIAM Symp. on Discr. Alg. (SODA), 2003, pp. 132-139 ·Zbl 1094.68605 |
| [11] | Bollobas, B.; Riordan, O., Mathematical results on scale-free random graphs, (Handbook of Graphs and Networks (2003), Wiley: Wiley Weinheim), 1-34 ·Zbl 1047.05038 |
| [12] | Bollobas, B.; Riordan, O., The diameter of a scale-free random graph, Combinatorica, 24, 5-34 (2004) ·Zbl 1047.05038 |
| [13] | Bollobas, B.; Riordan, O.; Spencer, J.; Tusnady, G., The degree sequence of a scale-free random graph process, Random Structures Algorithms, 18, 279-290 (2001) ·Zbl 0985.05047 |
| [14] | C. Borgs, J. Chayes, L. Lovász, Moments of two-variable functions and the uniqueness of graph limits, preprint, http://arxiv.org/abs/0803.1244; C. Borgs, J. Chayes, L. Lovász, Moments of two-variable functions and the uniqueness of graph limits, preprint, http://arxiv.org/abs/0803.1244 ·Zbl 1223.05193 |
| [15] | C. Borgs, J. Chayes, L. Lovász, V.T. Sós, K. Vesztergombi, unpublished, 2003; C. Borgs, J. Chayes, L. Lovász, V.T. Sós, K. Vesztergombi, unpublished, 2003 |
| [16] | Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Counting graph homomorphisms, (Klazar, M.; Kratochvil, J.; Loebl, M.; Matoušek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics (2006), Springer), 315-371 ·Zbl 1129.05050 |
| [17] | Borgs, C.; Chayes, J. T.; Lovász, L.; Sós, V. T.; Vesztergombi, K., Convergent graph sequences II. Multiway cuts and statistical physics (2007), preprint ·Zbl 1213.05161 |
| [18] | C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, K. Vesztergombi, Convergence of sparse graph sequences, in preparation; C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, K. Vesztergombi, Convergence of sparse graph sequences, in preparation |
| [19] | C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, B. Szegedy, K. Vesztergombi, Graph limits and parameter testing, in: Proc. of the 38th ACM Symp. Theory of Comp., 2006, pp. 261-270; C. Borgs, J.T. Chayes, L. Lovász, V.T. Sós, B. Szegedy, K. Vesztergombi, Graph limits and parameter testing, in: Proc. of the 38th ACM Symp. Theory of Comp., 2006, pp. 261-270 ·Zbl 1301.68199 |
| [20] | Chung, F.; Graham, R. L.; Wilson, R. M., Quasi-random graphs, Combinatorica, 9, 345-362 (1989) ·Zbl 0715.05057 |
| [21] | Erdös, P.; Lovász, L.; Spencer, J., Strong independence of graphcopy functions, (Graph Theory and Related Topics (1979), Academic Press), 165-172 ·Zbl 0462.05057 |
| [22] | E. Fischer, I. Newman, Testing versus estimation of graph properties, in: Proc. 37th Ann. ACM Symp. on Theory of Computing, Baltimore, MD, 2005, pp. 138-146; E. Fischer, I. Newman, Testing versus estimation of graph properties, in: Proc. 37th Ann. ACM Symp. on Theory of Computing, Baltimore, MD, 2005, pp. 138-146 ·Zbl 1192.68480 |
| [23] | Frieze, A.; Kannan, R., Quick approximation to matrices and applications, Combinatorica, 19, 175-220 (1999) ·Zbl 0933.68061 |
| [24] | Goldreich, O.; Goldwasser, S.; Ron, D., Property testing and its connection to learning and approximation, J. ACM, 45, 653-750 (1998) ·Zbl 1065.68575 |
| [25] | R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal, Stochastic models for the web graph, in: Proc. of the 41th ACM Found. of Comp. Sci. (FOCS), 2000, pp. 57-65; R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal, Stochastic models for the web graph, in: Proc. of the 41th ACM Found. of Comp. Sci. (FOCS), 2000, pp. 57-65 |
| [26] | Lovász, L.; Szegedy, B., Limits of dense graph sequences, J. Combin. Theory Ser. B, 96, 933-957 (2006) ·Zbl 1113.05092 |
| [27] | L. Lovász, B. Szegedy, Graph limits and testing hereditary graph properties, J. Math., in press, http://arxiv.org/abs/0803.1248; L. Lovász, B. Szegedy, Graph limits and testing hereditary graph properties, J. Math., in press, http://arxiv.org/abs/0803.1248 |
| [28] | Lovász, L.; Szegedy, B., Szemerédi’s lemma for the analyst, Geom. Func. Anal., 17, 252-270 (2007) ·Zbl 1123.46020 |
| [29] | Rudin, W., Real and Complex Analysis (1987), McGraw-Hill: McGraw-Hill New York ·Zbl 0925.00005 |
| [30] | E. Szemerédi, Regular partitions of graphs, in: J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau (Eds.), Colloque Inter. CNRS, 1978, pp. 399-401; E. Szemerédi, Regular partitions of graphs, in: J.-C. Bermond, J.-C. Fournier, M. Las Vergnas, D. Sotteau (Eds.), Colloque Inter. CNRS, 1978, pp. 399-401 ·Zbl 0413.05055 |
| [31] | Thomason, A., Pseudorandom graphs, (Random Graphs ’85. Random Graphs ’85, North-Holland Math. Stud., vol. 144 (1987), North-Holland: North-Holland Amsterdam), 307-331 ·Zbl 0632.05045 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
