Asymptotic structure of graphs with the minimum number of triangles. (English) Zbl 1371.05147
Summary: We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.
MSC:
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Aristoff, D. and Radin, C. (2013) Emergent structures in large networks. J. Appl. Probab.50883-888. doi:10.1017/S00219002000099183102521 · Zbl 1276.05106 |
| [2] | Bollobás, B., On complete subgraphs of different orders, Math. Proc. Camb. Phil. Soc., 79, 19-24, (1976) · Zbl 0325.05117 · doi:10.1017/S0305004100052063 |
| [3] | Borgs, C., Chayes, J., Lovász, L., Sós, V. T. and Vesztergombi, K. (2008) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math.2191801-1851. doi:10.1016/j.aim.2008.07.0082455626 · Zbl 1213.05161 |
| [4] | Chatterjee, S. and Dembo, A. (2014) Nonlinear large deviations. arXiv:1401.3495 · Zbl 1356.60045 |
| [5] | Chatterjee, S. and Dey, P. S. (2010) Applications of Stein’s method for concentration inequalities. Ann. Probab.382443-2485. doi:10.1214/10-AOP542 · Zbl 1203.60023 |
| [6] | Chatterjee, S. and Diaconis, P. (2013) Estimating and understanding exponential random graph models. Ann. Statist.412428-2461. doi:10.1214/13-AOS11553127871 · Zbl 1293.62046 |
| [7] | Chatterjee, S. and Varadhan, S. R. S. (2011) The large deviation principle for the Erdős-Rényi random graph. Europ. J. Combin.321000-1017. doi:10.1016/j.ejc.2011.03.014 · Zbl 1230.05259 |
| [8] | Cummings, J., Král’, D., Pfender, F., Sperfeld, K., Treglown, A. and Young, M. (2013) Monochromatic triangles in three-coloured graphs. J. Combin. Theory Ser. B103489-503. doi:10.1016/j.jctb.2013.05.0023071377 · Zbl 1301.05121 |
| [9] | Das, S., Huang, H., Ma, J., Naves, H. and Sudakov, B. (2013) A problem of Erdős on the minimum number of k-cliques. J. Combin. Theory Ser. B103344-373. doi:10.1016/j.jctb.2013.02.0033048160 · Zbl 1301.05185 |
| [10] | Erdős, P., Some theorems on graphs, Riveon Lematematika, 9, 13-17, (1955) |
| [11] | Erdős, P., On a theorem of Rademacher-Turán, Illinois J. Math., 6, 122-127, (1962) · Zbl 0099.39401 |
| [12] | Erdős, P. (1967) Some recent results on extremal problems in graph theory: Results. In Theory of Graphs: Rome 1966, Gordon and Breach, pp. 117-123 (English); pp. 124-130 (French). · Zbl 0187.21003 |
| [13] | Erdős, P., On the number of complete subgraphs and circuits contained in graphs, Časopis Pěst. Mat., 94, 290-296, (1969) · Zbl 0177.52502 |
| [14] | Erdős, P., Frankl, P. and Rödl, V. (1986) The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent. Graphs Combin.2113-121. doi:10.1007/BF01788085 · Zbl 0593.05038 |
| [15] | Fisher, D. C., Lower bounds on the number of triangles in a graph, J. Graph Theory, 13, 505-512, (1989) · Zbl 0673.05046 · doi:10.1002/jgt.3190130411 |
| [16] | Frieze, A. and Kannan, R. (1999) Quick approximation to matrices and applications. Combinatorica19175-220. doi:10.1007/s0049300500521723039 · Zbl 0933.68061 |
| [17] | Hatami, H., Hladký, J., Král’, D., Norine, S. and Razborov, A. (2013) On the number of pentagons in triangle-free graphs. J. Combin. Theory Ser. A120722-732. doi:10.1016/j.jcta.2012.12.0083007147 · Zbl 1259.05087 |
| [18] | Komlós, J. and Simonovits, M. (1996) Szemerédi’s regularity lemma and its applications to graph theory. In Combinatorics: Paul Erdős is Eighty (Miklós, D., Sós, V. T. and Szőnyi, T., eds), Vol. 2, Bolyai Mathematical Society, pp. 295-352. · Zbl 0851.05065 |
| [19] | Lovász, L. (2012) Large Networks and Graph Limits, Colloquium Publications, AMS. · Zbl 1292.05001 |
| [20] | Lovász, L. and Simonovits, M. (1976) On the number of complete subgraphs of a graph. In Proc. 5th British Combinatorial Conference: Aberdeen 1975. Congress. Numer.XV431-441. · Zbl 0339.05115 |
| [21] | Lovász, L. and Simonovits, M. (1983) On the number of complete subgraphs of a graph II. In Studies in Pure Mathematics, Birkhäuser, pp. 459-495. · Zbl 0519.05042 |
| [22] | Lovász, L. and Szegedy, B. (2006) Limits of dense graph sequences. J. Combin. Theory Ser. B96933-957. doi:10.1016/j.jctb.2006.05.0022274085 · Zbl 1113.05092 |
| [23] | Lubetzky, E. and Zhao, Y. (2014) On the variational problem for upper tails in sparse random graphs. arXiv:1402.6011 · Zbl 1364.05063 |
| [24] | Lubetzky, E. and Zhao, Y. (2015) On replica symmetry of large deviations in random graphs. Random Struct. Alg.47109-146. doi:10.1002/rsa.20536 · Zbl 1348.05195 |
| [25] | Mantel, W., Problem 28, Winkundige Opgaven, 10, 60-61, (1907) · JFM 38.0270.01 |
| [26] | Moon, J. W. and Moser, L. (1962) On a problem of Turán. Publ. Math. Inst. Hungar. Acad. Sci.7283-287. · Zbl 0114.01206 |
| [27] | Nikiforov, V., The number of cliques in graphs of given order and size, Trans. Amer. Math. Soc., 363, 1599-1618, (2011) · Zbl 1231.05129 · doi:10.1090/S0002-9947-2010-05189-X |
| [28] | Nordhaus, E. A. and Stewart, B. M. (1963) Triangles in an ordinary graph. Canad. J. Math.1533-41. doi:10.4153/CJM-1963-004-70151957 · Zbl 0115.17403 |
| [29] | Pikhurko, O., The minimum size of 3-graphs without four vertices spanning no or exactly three edges, Europ. J. Combin., 23, 1142-1155, (2011) · Zbl 1229.05154 |
| [30] | Pikhurko, O. and Vaughan, E. R. (2013) Minimum number of k-cliques in graphs with bounded independence number. Combin. Probab. Comput.22910-934. doi:10.1017/S09635483130003573111549 · Zbl 1282.05183 |
| [31] | Radin, C. and Sadun, L. (2013) Phase transitions in a complex network. J. Phys. A46305002. doi:10.1088/1751-8113/46/30/3050023083277 · Zbl 1314.82011 |
| [32] | Radin, C. and Yin, M. (2013) Phase transitions in exponential random graphs. Ann. Appl. Prob.232458-2471. doi:10.1214/12-AAP9073127941 · Zbl 1278.05225 |
| [33] | Radin, C., Ren, K. and Sadun, L. (2014) The asymptotics of large constrained graphs. J. Phys. A47175001. doi:10.1088/1751-8113/47/17/1750013197554 · Zbl 1290.05139 |
| [34] | Razborov, A., Flag algebras, J. Symbol. Logic, 72, 1239-1282, (2007) · Zbl 1146.03013 · doi:10.2178/jsl/1203350785 |
| [35] | Razborov, A., On the minimal density of triangles in graphs, Combin. Probab. Comput., 17, 603-618, (2008) · Zbl 1170.05036 |
| [36] | Reiher, C. (2012) The clique density theorem. arXiv:1212.2454 · Zbl 1348.05103 |
| [37] | Ruzsa, I. Z. and Szemerédi, E. (1978) Triple systems with no six points carrying three triangles. In Combinatorics II (Hajnal, A. and Sós, V., eds), North-Holland, pp. 939-945. · Zbl 0393.05031 |
| [38] | Simonovits, M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs: Tihany 1966, Academic, pp. 279-319. · Zbl 0164.24604 |
| [39] | Turán, P., On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok, 48, 436-452, (1941) · JFM 67.0732.03 |
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.
