A Spectral Erdős–Faudree–Rousseau Theorem
Yongtao Li
School of Mathematics and Statistics, Central South University, Changsha, China
Search for more papers by this authorCorresponding Author
Lihua Feng
School of Mathematics and Statistics, Central South University, Changsha, China
Correspondence: Lihua Feng ([email protected])
Yuejian Peng ([email protected])
Search for more papers by this authorCorresponding Author
Yuejian Peng
School of Mathematics, Hunan University, Changsha, China
Correspondence: Lihua Feng ([email protected])
Yuejian Peng ([email protected])
Search for more papers by this authorYongtao Li
School of Mathematics and Statistics, Central South University, Changsha, China
Search for more papers by this authorCorresponding Author
Lihua Feng
School of Mathematics and Statistics, Central South University, Changsha, China
Correspondence: Lihua Feng ([email protected])
Yuejian Peng ([email protected])
Search for more papers by this authorCorresponding Author
Yuejian Peng
School of Mathematics, Hunan University, Changsha, China
Correspondence: Lihua Feng ([email protected])
Yuejian Peng ([email protected])
Search for more papers by this authorABSTRACT
A well-known theorem of Mantel states that every -vertex graph with more than edges contains a triangle. An interesting problem in extremal graph theory studies the minimum number of edges contained in triangles among graphs with a prescribed number of vertices and edges. Erdős, Faudree, and Rousseau (1992) showed that a graph on vertices with more than edges contains at least edges in triangles. Such edges are called triangular edges. In this paper, we present a spectral version of the result of Erdős, Faudree, and Rousseau. Using the supersaturation-stability and the spectral technique, we prove that every -vertex graph with contains at least triangular edges, unless is a balanced complete bipartite graph. The method in our paper has some interesting applications. Firstly, the supersaturation-stability can be used to revisit a conjecture of Erdős concerning the booksize of a graph, which was initially proved by Edwards (unpublished), and independently by Khadžiivanov and Nikiforov (1979). Secondly, our method can improve the bound on the order of the spectral extremal graph when we forbid the friendship graph as a substructure. We drop the condition that requires the order to be sufficiently large, which was investigated by Cioabă et al. (2020) using the triangle removal lemma. Thirdly, this method can be utilized to deduce the classical stability for odd cycles, and it gives more concise bounds on parameters. Finally, supersaturation stability could be applied to deal with the spectral graph problems on counting triangles, which was recently studied by Ning and Zhai (2023).
Open Research
Data Availability Statement
The authors have nothing to report.
References
- 1B. Bollobás, Extremal Graph Theory (Academic Press, 1978).
- 2P. Erdős, “Some Theorems on Graphs,” Riveon Lematematika 9 (1955): 13–17.
- 3P. Erdős, “On the Number of Triangles Contained in Certain Graphs,” Canadian Mathematical Bulletin 7, no. 1 (1964): 53–56.
10.4153/CMB-1964-007-3 Google Scholar
- 4P. Erdős, “On a Theorem of Rademacher-Turán,” Illinois Journal of Mathematics 6 (1962): 122–127.
10.1215/ijm/1255631811 Google Scholar
- 5P. Erdős, “On the Number of Complete Subgraphs Contained in Certain Graphs,” A Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei 7 (1962): 459–474.
- 6L. Lovász and M. Simonovits, “On the Number of Complete Subgraphs of a Graph,” in Proceedings of Fifth British Combinatorial Conference (Aberdeen, 1975), 431–442.
- 7L. Lovász and M. Simonovits, “On the Number of Complete Subgraphs of a Graph II,” in Studies in Pure Math, Birkhäuser (dedicated to P. Turán, 1983), 459–495.
- 8C. Xiao and G. O. Katona, “The Number of Triangles Is More When They Have No Common Vertex,” Discrete Mathematics 344 (2021): 112330.
- 9X. Liu and D. Mubayi, “On a Generalized Erdős-Rademacher Problem,” Journal of Graph Theory 100 (2022): 101–126.
- 10J. Balogh and F. C. Clemen, “On Stability of the Erdős-Rademacher Problem,” Illinois Journal of Mathematics 67, no. 1 (2023): 1–11.
10.1215/00192082-10429321 Google Scholar
- 11A. Razborov, “On the Minimal Density of Triangles in Graphs,” Combinatorics, Probability and Computing 17, no. 4 (2008): 603–618.
- 12V. Nikiforov, “The Number of Cliques in Graphs of Given Order and Size,” Transactions of the American Mathematical Society 363, no. 3 (2011): 1599–1618.
- 13C. Reiher, “The Clique Density Theorem,” Annals of Mathematics 184, no. 3 (2016): 683–707.
- 14H. Liu, O. Pikhurko, and K. Staden, “The Exact Minimum Number of Triangles in Graphs of Given Order and Size,” Forum of Mathematics 8, no. e8 (2020): 144.
- 15D. Mubayi, “Counting Substructures I: Color Critical Graphs,” Advances in Mathematics 225, no. 5 (2010): 2731–2740.
- 16O. Pikhurko and Z. Yilma, “Supersaturation Problem for Color-Critical Graphs,” Journal of Combinatorial Theory, Series B 123 (2017): 148–185.
- 17P. Erdős, R. Faudree, and C. Rousseau, “Extremal Problems Involving Vertices and Edges on Odd Cycles,” Discrete Mathematics 101, no. 1 (1992): 23–31.
- 18Z. Füredi and Z. Maleki, “The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs,” Combinatorics, Probability and Computing 26 (2017): 525–535.
- 19V. Gruslys and S. Letzter, “Minimizing the Number of Triangular Edges,” Combinatorics, Probability and Computing 27 (2018): 580–622.
- 20A. Grzesik, P. Hu, and J. Volec, “Minimum Number of Edges That Occur in Odd Cycles,” Journal of Combinatorial Theory, Series B 137 (2019): 65–103.
- 21H. Wilf, “Spectral Bounds for the Clique and Indendence Numbers of Graphs,” Journal of Combinatorial Theory, Series B 40 (1986): 113–117.
10.1016/0095-8956(86)90069-9 Google Scholar
- 22V. Nikiforov, “Some Inequalities for the Largest Eigenvalue of a Graph,” Combinatorics, Probability and Computing 11 (2002): 179–189.
- 23V. Nikiforov, “Bounds on Graph Eigenvalues II,” Linear Algebra and its Applications 427 (2007): 183–189.
- 24Y. Li and Y. Peng, “Refinement on Spectral Turán's Theorem,” SIAM Journal of Discrete Mathematics 37, no. 4 (2023): 2462–2485.
10.1137/22M1507814 Google Scholar
- 25B. Bollobás and V. Nikiforov, “Cliques and the Spectral Radius,” Journal of Combinatorial Theory, Series B 97 (2007): 859–865.
- 26H. Lin, B. Ning, and B. Wu, “Eigenvalues and Triangles in Graphs,” Combinatorics, Probability and Computing 30, no. 2 (2021): 258–270.
- 27S. Zhang, “On the First Two Eigenvalues of Regular Graphs,” Linear Algebra and Its Applications 686 (2024): 102–110.
- 28C. Elphick, W. Linz, and P. Wocjan, “Two Conjectured Strengthenings of Turán's Theorem,” Linear Algebra and Its Applications 684 (2024): 23–36.
- 29M. Zhai and J. Shu, “A Spectral Version of Mantel's Theorem,” Discrete Mathematics 345 (2022): 112630.
- 30Y. Li, L. Feng, and Y. Peng, “A Spectral Extremal Problem on Non-Bipartite Triangle-Free Graphs,” Electronic Journal of Combinatorics 31, no. 1 (2024): #P1.52.
- 31M. Tait and J. Tobin, “Three Conjectures in Extremal Spectral Graph Theory,” Journal of Combinatorial Theory, Series B 126 (2017): 137–161.
- 32H. Lin and B. Ning, “A Complete Solution to the Cvetković-Rowlinson Conjecture,” Journal of Graph Theory 97, no. 3 (2021): 441–450.
- 33V. Nikiforov, “A Spectral Erdős-Stone-Bollobás Theorem,” Combinatorics, Probability and Computing 18 (2009): 455–458.
- 34V. Nikiforov, “Stability for Large Forbidden Subgraphs,” Journal of Graph Theory 62, no. 4 (2009): 362–368.
- 35S. Cioabă, D. N. Desai, and M. Tait, “The Spectral Even Cycle Problem,” Combinatorial Theory 4, no. 1 (2024): #10.
- 36X. Li, M. Zhai, J. Shu, and A Brualdi-Hoffman-Turán, “Problem on Cycles,” European Journal of Combinatorics 120 (2024): 103966.
- 37S. Cioabă, D. N. Desai, and M. Tait, “A Spectral Erdős-Sós Theorem,” SIAM Journal of Discrete Mathematics 37, no. 3 (2023): 2228–2239.
- 38L. Fang, H. Lin, J. Shu, and Z. Zhang, “Spectral Extremal Results on Trees,” Electronic Journal of Combinatorics 31, no. 2 (2024): #P2.34.
- 39M. Zhai and R. Liu, “ A Spectral Erdős-Pósa Theorem,” (2022).
- 40M. Zhai and H. Lin, “A Strengthening of the Spectral Color Critical Edge Theorem: Books and Theta Graphs,” Journal of Graph Theory 102, no. 3 (2023): 502–520.
- 41V. Nikiforov, “ On a Theorem of Nosal,” (2021).
- 42B. Li and B. Ning, “Eigenvalues and Cycles of Consecutive Lengths,” Journal of Graph Theory 103, no. 3 (2023): 486–492.
- 43W. Zhang, “The Spectral Radius, Maximum Average Degree and Cycles of Consecutive Lengths of Graphs,” Graphs and Combinatorics 40, no. 2 (2024): 32.
- 44J. Wang, L. Kang, and Y. Xue, “On a Conjecture of Spectral Extremal Problems,” Journal of Combinatorial Theory Series B 159 (2023): 20–41.
- 45M. Tait, “The Colin de Verdiére Parameter, Excluded Minors, and the Spectral Radius,” Journal of Combinatorial Theory Series A 166 (2019): 42–58.
- 46M. Zhai and H. Lin, “Spectral Extrema of Ks,t-Minor Free Graphs —on a Conjecture of M. Tait,” Journal of Combinatorial Theory Series B 157 (2022): 184–215.
10.1016/j.jctb.2022.07.002 Google Scholar
- 47B. Ning and M. Zhai, “Counting Substructures and Eigenvalues I: Triangles,” European Journal of Combinatorics 110 (2023): 103685.
- 48Y. Li, L. Lu, and Y. Peng, “A Spectral Erdős-Rademacher Theorem,” Advances in Applied Mathematics 158 (2024): 102720.
- 49S. Cioabă, L. Feng, M. Tait, and X.-D. Zhang, “The Maximum Spectral Radius of Graphs Without Friendship Subgraphs,” Electronic Journal of Combinatorics 27, no. 4 (2020): #P4.22.
- 50Y. Li and Y. Peng, “The Spectral Radius of Graphs With no Intersecting Odd Cycles,” Discrete Mathematics 345 (2022): 112907.
- 51D. N. Desai, L. Kang, Y. Li, Z. Ni, M. Tait, and J. Wang, “Spectral Extremal Graphs for Intersecting Cliques,” Linear Algebra and Its Applications 644 (2022): 234–258.
- 52D. Cvetković, P. Rowlinson, and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, 2010), 83–87.
- 53L. Lovász, Combinatorial Problems and Exercises, 2nd ed. (North-Holland Publishing Co., 1979/1993).
- 54D. Conlon and J. Fox, “Graph Removal Lemmas,” in Surveys in Combinatorics, London Math. Soc. Lecture Note Ser., vol. 409 (Cambridge University Press, 2013), 1–49.
- 55M. Simonovits, “A Method for Solving Extremal Problems in Graph Theory, Stability Problems,” in Theory of Graphs, Proc. Colloq., Tihany, 1966 (Academic Press, 1968), 279–319.
- 56Z. Füredi, “A Proof of the Stability of Extremal Graphs,” Simonovits' Stability From Szemerédi's Regularity, Journal Combinatorial Theory Series B 115 (2015): 66–71.
- 57N. Alon, S. Das, R. Glebov, and B. Sudakov, “Comparable Pairs in Families of Sets,” Journal of Combinatorial Theory, Series B 115 (2015): 164–185.
- 58D. Conlon, J. Fox, and B. Sudakov, “Short Proofs of Some Extremal Results III,” Random Structures & Algorithms 57 (2020): 958–982.
- 59J. Fox, X. He, and Y. Wigderson, “Ramsey Goodness of Books Revisted,” Advances in Combinatorics 4 (2023): 21.
- 60J. Moon and L. Moser, “On a Problem of Turán,” Magyar Tudományos Akadémia. Matematikai Kutató Intézetének Közleményei 7 (1962): 283–286.
- 61J. Balogh, N. Bushaw, M. Collares, H. Liu, R. Morris, and M. Sharifzadeh, “The Typical Structure of Graphs With no Large Cliques,” Combinatorica 37, no. 4 (2017): 617–632.
- 62B. Sudakov, “Making a -Free Graph Bipartite,” Combinatorica 27, no. 4 (2007): 509–518.
10.1007/s00493-007-2238-0 Google Scholar
- 63D. Conlon, J. Fox, and B. Sudakov, “Books Versus Triangles at the Extremal Density,” SIAM Journal of Discrete Mathematics 34 (2020): 385–398.
- 64N. Khadziivanov and V. Nikiforov, “Solution of a Problem of P. Erdős About the Maximum Number of Triangles With a Common Edge in a Graph,” [in Russian], Comptes rendus de l'Academie bulgare des Sciences 32 (1979): 1315–1318.
- 65B. Bollobás and V. Nikiforov, “Books in Graphs,” European Journal of Combinatorics 26 (2005): 259–270.
- 66N. Alon and C. Shikhelman, “Many Copies in -Free Graphs,” Journal of Combinatorics Theory, Series B 121 (2016): 146–172.
10.1016/j.jctb.2016.03.004 Google Scholar
- 67Y. Li, L. Lu, and Y. Peng, “Spectral Extremal Graphs for the Bowtie,” Discrete Mathematics 346 (2023): 113680.
- 68H. Lin, M. Zhai, and Y. Zhao, “Spectral Radius, Edge-Disjoint Cycles and Cycles of the Same Length,” Electronic Journal of Combinatorics 29, no. 2 (2022): #P2.1.
- 69A. Roberts and A. Scott, “Stability Results for Graphs With a Critical Edge,” Electronic Journal of Combinatorics 74 (2018): 27–38.
10.1016/j.ejc.2018.07.004 Google Scholar
- 70X. Liu, “New Short Proofs to Some Stability Theorems,” Electronic Journal of Combinatorics 96 (2021): 103350.
10.1016/j.ejc.2021.103350 Google Scholar
- 71J. Balogh, F. C. Clemen, M. Lavrov, B. Lidický, and F. Pfender, “Making -Free Graphs -Partite,” Combinatorics, Probability and Computing 30, no. 4 (2021): 609–618.
10.1017/S0963548320000590 Google Scholar
- 72D. Korándi, A. Roberts, and A. Scott, “Exact Stability for Turán Theorem,” Advances in Combinatorics 9 (2021): 17.
- 73X. Zhu, Y. Chen, D. Gerbner, E. Győri, and H. H. Karim, “The Maximum Number of Triangles in -Free Graphs,” European Journal of Combinatorics 114 (2023): 103793.
10.1016/j.ejc.2023.103793 Google Scholar
- 74P. Erdős, Z. Füredi, R. J. Gould, and D. S. Gunderson, “Extremal Graphs for Intersecting Triangles,” Journal of Combinatorial Theory, Series B 64 (1995): 89–100.
- 75Z. Füredi and D. S. Gunderson, “Extremal Numbers for Odd Cycles,” Combinatorics, Probability and Computing 24, no. 4 (2015): 641–645.
- 76E. Nosal, “Eigenvalues of Graphs,” (Master's thesis, University of Calgary, 1970).
- 77B. Ning, “On Some Papers of Nikiforov,” Ars Combinatoria 135 (2017): 187–195.