Geodesic
THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
Forum of Mathematics, Pi, Tome 8 (2020)

Voir la notice de l'article provenant de la source Cambridge University Press

What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, Rademacher solved the first nontrivial case of this problem in 1941. The problem was revived by Erdős in 1955; it is now known as the Erdős–Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from $1$, which in this range confirms a conjecture of Lovász and Simonovits from 1975. Furthermore, we give a description of the extremal graphs. 
@article{10_1017_fmp_2020_7,
     author = {HONG LIU and OLEG PIKHURKO and KATHERINE STADEN},
     title = {THE {EXACT} {MINIMUM} {NUMBER} {OF} {TRIANGLES} {IN} {GRAPHS} {WITH} {GIVEN} {ORDER} {AND} {SIZE}},
     journal = {Forum of Mathematics, Pi},
     publisher = {mathdoc},
     volume = {8},
     year = {2020},
     doi = {10.1017/fmp.2020.7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fmp.2020.7/}
}
TY  - JOUR
AU  - HONG LIU
AU  - OLEG PIKHURKO
AU  - KATHERINE STADEN
TI  - THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
JO  - Forum of Mathematics, Pi
PY  - 2020
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fmp.2020.7/
DO  - 10.1017/fmp.2020.7
LA  - en
ID  - 10_1017_fmp_2020_7
ER  - 
%0 Journal Article
%A HONG LIU
%A OLEG PIKHURKO
%A KATHERINE STADEN
%T THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE
%J Forum of Mathematics, Pi
%D 2020
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fmp.2020.7/
%R 10.1017/fmp.2020.7
%G en
%F 10_1017_fmp_2020_7
HONG LIU; OLEG PIKHURKO; KATHERINE STADEN. THE EXACT MINIMUM NUMBER OF TRIANGLES IN GRAPHS WITH GIVEN ORDER AND SIZE. Forum of Mathematics, Pi, Tome 8 (2020). doi: 10.1017/fmp.2020.7

[1] Bollobás, B., ‘On complete subgraphs of different orders’, Math. Proc. Cambridge Philos. Soc. 79 (1976), 19–24.Google Scholar | DOI

[2] Conlon, D., Fox, J. and Sudakov, B., ‘An approximate version of Sidorenko’s conjecture’, Geom. Funct. Anal. 20 (2010), 1354–1366.Google Scholar | DOI

[3] Conlon, D., Kim, J. H., Lee, C. and Lee, J., ‘Some advances on Sidorenko’s conjecture’, J. Lond. Math. Soc. 98 (2018), 593–608.Google Scholar | DOI

[4] Csikvári, P., ‘Note on the smallest root of the independence polynomial’, Combin. Probab. Comput. 22 (2013), 1–8.Google Scholar | DOI

[5] Erdős, P. and Simonovits, M., ‘Supersaturated graphs and hypergraphs’, Combinatorica 3 (1983), 181–192.Google Scholar | DOI

[6] Erdős, P., ‘Some theorems on graphs’, Riveon Lematematika 9 (1955), 13–17.Google Scholar

[7] Erdős, P., ‘On a theorem of Rademacher–Turán’, Illinois. J. Maths 6 (1962), 122–127.Google Scholar | DOI

[8] Erdős, P., ‘Some recent results on extremal problems in graph theory. Results’, inTheory of Graphs (Internat. Sympos., Rome, 1966) (Gordon and Breach, New York, 1967), 117–123. (English); pp 124–130 (French).Google Scholar

[9] Erdős, P. and Stone, A. H., ‘On the structure of linear graphs’, Bull. Amer. Math. Soc. (N.S.) 52 (1946), 1087–1091.Google Scholar | DOI

[10] Fisher, D. C., ‘Lower bounds on the number of triangles in a graph’, J. Graph Theory 13 (1989), 505–512.Google Scholar | DOI

[11] Glebov, R., Grzesik, A., Hu, P., Hubai, T., Král’, D. and Volec, J., ‘Densities of 3-vertex graphs’, Preprint, 2016, .Google Scholar

[12] Goldwurm, M. and Santini, M., ‘Clique polynomials have a unique root of smallest modulus’, Inform. Process. Lett. 75 (2000), 127–132.Google Scholar | DOI

[13] Goodman, A. W., ‘On sets of acquaintances and strangers at any party’, Amer. Math. Monthly 66 (1959), 778–783.Google Scholar | DOI

[14] Harangi, V., ‘On the density of triangles and squares in regular finite and unimodular random graphs’, Combinatorica 33 (2013), 531–548.Google Scholar | DOI

[15] Hatami, H., ‘Graph norms and Sidorenko’s conjecture’, Israel J. Math. 175 (2010), 125–150.Google Scholar | DOI

[16] Hatami, H. and Norine, S., ‘Undecidability of linear inequalities in graph homomorphism densities’, J. Amer. Math. Soc. 24 (2011), 547–565.Google Scholar | DOI

[17] Hatami, H. and Norine, S., ‘On the boundary of the region defined by homomorphism densities’, J. Combin. 10 (2019), 203–219.Google Scholar

[18] Huang, H., Linial, N., Naves, H., Peled, Y. and Sudakov, B., ‘On the 3-local profiles of graphs’, J. Graph Theory 76 (2014), 236–248.Google Scholar | DOI

[19] Kang, M., Makai, T. and Pikhurko, O., ‘Supersaturation problem for the bowtie’, Eur. J. Combin. (2017), in press, doi:10.1016/j.ejc.2020.103107.Google Scholar

[20] Katona, G. O. H., ‘Intersection theorems for systems of finite sets’, Acta Math. Acad. Sci. Hung. 15 (1964), 329–337.Google Scholar | DOI

[21] Kim, J., Liu, H., Pikhurko, O. and Sharifzadeh, M., ‘Asymptotic structure for the clique density theorem’, Preprint, 2019, .Google Scholar

[22] Kim, J. H., Lee, C. and Lee, J., ‘Two approaches to Sidorenko’s conjecture’, Trans. Amer. Math. Soc. 368 (2016), 5057–5074.Google Scholar | DOI

[23] Kruskal, J. B., ‘The number of simplices in a complex’, inMathematical Optimization Techniques (ed. Bellman, R.) (University California Press, Berkeley, 1963), 251–278.Google Scholar

[24] Li, J. L. X. and Szegedy, B., ‘On the logarithmic calculus and Sidorenko’s conjecture’, Combinatorica (2011), to appear.Google Scholar

[25] Lovász, L. and Simonovits, M., ‘On the number of complete subgraphs of a graph’, inProceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) (Congressus Numerantium, No. XV, Winnipeg, Man, 1976), 431–441. Utilitas Math.Google Scholar

[26] Lovász, L. and Simonovits, M., ‘On the number of complete subgraphs of a graph. II’, inStudies in Pure Mathematics (Birkhäuser, Basel, 1983), 459–495.Google Scholar | DOI

[27] Mantel, W., ‘Problem 28’, Winkundige Opgaven 10 (1907), 60–61.Google Scholar

[28] Moon, J. W. and Moser, L., ‘On a problem of Turán’, Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962), 283–287.Google Scholar

[29] Mubayi, D., ‘Counting substructures I: color critical graphs’, Adv. Math. 225 (2010), 2731–2740.Google Scholar | DOI

[30] Nikiforov, V., ‘The number of cliques in graphs of given order and size’, Trans. Amer. Math. Soc. 363 (2011), 1599–1618.Google Scholar | DOI

[31] Nikiforov, V. S., ‘On a problem of P Erdős’, Annuaire Univ. Sofia Fac. Math. Méc. 71 (1976/77), 157–160.Google Scholar

[32] Nikiforov, V. S. and Khadzhiivanov, N. G., ‘Solution of the problem of P. Erdős on the number of triangles in graphs with n vertices and [n 2/4] + l edges’, C. R. Acad. Bulgare Sci. 34 (1981), 969–970.Google Scholar

[33] Nordhaus, E. A. and Stewart, B. M., ‘Triangles in an ordinary graph’, Canad. J. Math. 15 (1963), 33–41.Google Scholar | DOI

[34] Pikhurko, O. and Razborov, A., ‘Asymptotic structure of graphs with the minimum number of triangles’, Combin. Probab. Comput. 26 (2017), 138–160.Google Scholar | DOI

[35] Pikhurko, O. and Yilma, Z., ‘Supersaturation problem for color-critical graphs’, J. Combin. Theory B 123 (2017), 148–185.Google Scholar | DOI

[36] Razborov, A., ‘Flag algebras’, J. Symb. Logic 72 (2007), 1239–1282.Google Scholar | DOI

[37] Razborov, A., ‘On the minimal density of triangles in graphs’, Combin. Probab. Comput. 17 (2008), 603–618.Google Scholar | DOI

[38] Reiher, C., ‘The clique density theorem’, Ann. of Math. (2) 184 (2016), 683–707.Google Scholar | DOI

[39] Sidorenko, A. F., ‘A correlation inequality for bipartite graphs’, Graphs Combin. 9 (1993), 201–204.Google Scholar | DOI

[40] Simonovits, M., ‘A method for solving extremal problems in graph theory, stability problems’, inTheory of Graphs (Proc. Colloq., Tihany, 1966) (Academic Press, New York, 1968), 279–319.Google Scholar

[41] Szegedy, B., ‘An information theoretic approach to Sidorenko’s conjecture’, Preprint, 2014, .Google Scholar

[42] Turán, P., ‘On an extremal problem in graph theory (in Hungarian)’, Mat. Fiz. Lapok 48 (1941), 436–452.Google Scholar

Cité par Sources :