Geodesic
On extremal numbers of the triangle plus the four-cycle
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e154

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

For a family $\mathcal {F}$ of graphs, let ${\mathrm {ex}}(n,\mathcal {F})$ denote the maximum number of edges in an n-vertex graph which contains none of the members of $\mathcal {F}$ as a subgraph. A longstanding problem in extremal graph theory asks to determine the function ${\mathrm {ex}}(n,\{C_3,C_4\})$. Here we give a new construction for dense graphs of girth at least five with arbitrary number of vertices, providing the first improvement on the lower bound of ${\mathrm {ex}}(n,\{C_3,C_4\})$ since 1976. As a corollary, this yields a negative answer to a problem in Chung-Graham [3]. 
Ma, Jie; Yang, Tianchi. On extremal numbers of the triangle plus the four-cycle. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e154. doi: 10.1017/fms.2025.10100
@article{10_1017_fms_2025_10100,
     author = {Ma, Jie and Yang, Tianchi},
     title = {On extremal numbers of the triangle plus the four-cycle},
     journal = {Forum of Mathematics, Sigma},
     pages = {e154},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10100},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10100/}
}
TY  - JOUR
AU  - Ma, Jie
AU  - Yang, Tianchi
TI  - On extremal numbers of the triangle plus the four-cycle
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e154
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10100/
DO  - 10.1017/fms.2025.10100
ID  - 10_1017_fms_2025_10100
ER  - 
%0 Journal Article
%A Ma, Jie
%A Yang, Tianchi
%T On extremal numbers of the triangle plus the four-cycle
%J Forum of Mathematics, Sigma
%D 2025
%P e154
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10100/
%R 10.1017/fms.2025.10100
%F 10_1017_fms_2025_10100

[1] Allen, P., Keevash, P., Sudakov, B. and Verstraëte, J., ‘Turán numbers of bipartite graphs plus an odd cycle’, J. Combin. Theory Ser. B 106 (2014), 134–162. doi:10.1016/j.jctb.2014.01.007 Google Scholar | DOI

[2] Baker, R. C., Harman, G. and Pintz, J., ‘The difference between consecutive primes’, Proc. Lond. Math. Soc. II 83(3) (2001), 532–562. doi:10.1112/plms/83.3.532 Google Scholar | DOI

[3] Chung, F. and Graham, R., Erdős on Graphs: His Legacy of Unsolved Problems (A. K. Peters, Wellesley, MA, 1998).10.1201/9781439863879 Google Scholar | DOI

[4] Damásdi, G., Héger, T. and Szőnyi, T., ‘The Zarankiewicz problem, cages, and geometries’, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 56 (2013), 3–37. Google Scholar

[5] Erdős, P., ‘On sequences of integers no one of which divides the product of two others and on some related problems’, Mitt. Forsch.-Inst. Math. Mech. Univ. Tomsk 2 (1938), 74–82. Google Scholar

[6] Erdős, P., ‘Some recent progress on extremal problems in graph theory’, Congr. Numer. 14 (1975), 3–14. Google Scholar

[7] Erdős, P. and Simonovits, M., ‘Compactness results in extremal graph theory’, Combinatorica 2 (1982), 275–288. doi:10.1007/bf02579234 Google Scholar | DOI

[8] Füredi, Z., ‘New asymptotics for bipartite Turán numbers’, J. Combin. Theory Ser. A 75 (1996), 141–144. doi:10.1006/jcta.1996.0067 Google Scholar | DOI

[9] Füredi, Z. and Simonovits, M., ‘The history of the degenerate (bipartite) extremal graph problems’, Bolyai Soc. Math. Stud. 25 (2013), 169–264. Erdős Centennial (J. Bolyai Mathematical Society). doi:10.1007/978-3-642-39286-3_7 Google Scholar | DOI

[10] Garnick, D. K., Kwong, Y. H. and Lazebnik, F., ‘Extremal graphs without three-cycles or four-cycles’, J. Graph Theory 17(5) (1993), 633–645. doi:10.1002/jgt.3190170511 Google Scholar | DOI

[11] Heath-Brown, R., ‘The differences between consecutive primes, V’, Int. Math. Res. Not. 22 (2021), 17514–17562. doi:10.1112/plms/83.3.532 Google Scholar | DOI

[12] Keevash, P., Sudakov, B. and Verstraëte, J., ‘On a conjecture of Erdős and Simonovits: Even cycles’, Combinatorica 33 (2013), 699–732. doi:10.1007/s00493-013-2863-8 Google Scholar | DOI

[13] Kővári, T., Sós, V. and Turán, P., ‘On a problem of K. Zarankiewicz’, Colloq. Math. 3 (1954), 50–57.10.4064/cm-3-1-50-57 Google Scholar | DOI

[14] Parsons, T. D., ‘Graphs from projective planes’, Aequationes Math. 14 (1976), 167–189. doi:10.1007/bf01834128 Google Scholar | DOI

[15] Reiman, I., ‘Über ein Problem von K. Zarankiewicz’, Acta Math. Acad. Sci. Hung. 9 (1958), 269–278. doi:10.1007/bf02020254 Google Scholar | DOI

Cité par Sources :