Geodesic
Density of monochromatic infinite subgraphs II
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e91

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

In 1967, Gerencsér and Gyárfás [16] proved a result which is considered the starting point of graph-Ramsey theory: In every 2-coloring of $K_n$, there is a monochromatic path on $\lceil (2n+1)/3\rceil $ vertices, and this is best possible. There have since been hundreds of papers on graph-Ramsey theory with some of the most important results being motivated by a series of conjectures of Burr and Erdős [2, 3] regarding the Ramsey numbers of trees (settled in [31]), graphs with bounded maximum degree (settled in [5]), and graphs with bounded degeneracy (settled in [23]).In 1993, Erdős and Galvin [13] began the investigation of a countably infinite analogue of the Gerencsér and Gyárfás result: What is the largest d such that in every $2$-coloring of $K_{\mathbb {N}}$ there is a monochromatic infinite path with upper density at least d? Erdős and Galvin showed that $2/3\leq d\leq 8/9$, and after a series of recent improvements, this problem was finally solved in [7] where it was shown that $d={(12+\sqrt {8})}/{17}$.This paper begins a systematic study of quantitative countably infinite graph-Ramsey theory, focusing on infinite analogues of the Burr-Erdős conjectures. We obtain some results which are analogous to what is known in finite case, and other (unexpected) results which have no analogue in the finite case. 
Corsten, Jan; DeBiasio, Louis; McKenney, Paul. Density of monochromatic infinite subgraphs II. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e91. doi: 10.1017/fms.2025.42
@article{10_1017_fms_2025_42,
     author = {Corsten, Jan and DeBiasio, Louis and McKenney, Paul},
     title = {Density of monochromatic infinite subgraphs {II}},
     journal = {Forum of Mathematics, Sigma},
     pages = {e91},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.42},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.42/}
}
TY  - JOUR
AU  - Corsten, Jan
AU  - DeBiasio, Louis
AU  - McKenney, Paul
TI  - Density of monochromatic infinite subgraphs II
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e91
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.42/
DO  - 10.1017/fms.2025.42
ID  - 10_1017_fms_2025_42
ER  - 
%0 Journal Article
%A Corsten, Jan
%A DeBiasio, Louis
%A McKenney, Paul
%T Density of monochromatic infinite subgraphs II
%J Forum of Mathematics, Sigma
%D 2025
%P e91
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.42/
%R 10.1017/fms.2025.42
%F 10_1017_fms_2025_42

[1] Allen, P., Brightwell, G. and Skokan, J., ‘Ramsey-goodness – and otherwise’, Combinatorica 33(2) (2013), 125–160. Google Scholar | DOI

[2] Burr, S. A. and Erdős, P., ‘On the magnitude of generalized Ramsey numbers for graphs’, Colloq. Math. Soc. János Bolyai 10 (1975), 215–240. Google Scholar

[3] Burr, S. A. and Erdős, P., ‘Extremal Ramsey theory for graphs’, Util. Math. 9 (1976), 247–258. An International Journal of Discrete and Combinatorial Mathematics, and Statistical Design. Google Scholar

[4] Cameron, P. J., ‘The random graph’, in The Mathematics of Paul Erdős II (Springer, New York, 2013), pp. 353–378. Google Scholar | DOI

[5] Chvatál, C., Rödl, V., Szemerédi, E. and Trotter, W. T. Jr., ‘The Ramsey number of a graph with bounded maximum degree’, J. Combin. Theory Ser. B 34(3) (1983), 239–243. Google Scholar | DOI

[6] Conlon, D., Fox, J. and Sudakov, B., ‘Recent developments in graph Ramsey theory’, in Surveys in Combinatorics 2015 (London Math. Soc. Lecture Note Ser.) vol. 424 (Springer, Berlin, 2015), 49–118. Google Scholar | DOI

[7] Corsten, J., Debiasio, L., Lamaison, A. and Lang, R., ‘Upper density of monochromatic infinite paths’, Adv. Comb. 4 (2019), 16 pp. Google Scholar

[8] Day, A. N. and Lo, A., ‘Upper density of monochromatic paths in edge-coloured infinite complete graphs and bipartite graphs’, Preprint, 2022, . Google Scholar | arXiv | DOI

[9] Debiasio, L. and Gyárfás, A., ‘Covering 2-colored complete digraphs by monochromatic -dominating digraphs’, J. Graph Theory 100(4) (2022), 721–726. Google Scholar | DOI

[10] Debiasio, L. and Mckenney, P., ‘Density of monochromatic infinite subgraphs’, Combinatorica 39(4) (2019), 847–878. Google Scholar | DOI

[11] Diestel, R., Graph Theory, third edn. (Graduate Texts in Mathematics) vol. 173 (Cambridge University Press, Cambridge, 2005). Google Scholar

[12] Elekes, M., Soukup, D. T., Soukup, L. and Szentmiklóssy, Z., ‘Decompositions of edge-colored infinite complete graphs into monochromatic paths’, Discrete Math. 340(8) (2017), 2053–2069. Google Scholar | DOI

[13] Erdős, P. and Galvin, F., ‘Monochromatic infinite paths’, Discrete Math. 113(1–3) (1993), 59–70. Google Scholar | DOI

[14] Erdős, P., Faudree, R., Rousseau, C. and Schelp, R., ‘Ramsey numbers for brooms’, in Combinatorics, Graph Theory and Computing, Proceedings of 13th Southeast. Conference, Boca Raton 1982, Congr. Numerantium 35 (1982), 283–293. Google Scholar

[15] Faudree, R. J. and Schelp, R. H., ‘Path-path Ramsey-type numbers for the complete bipartite graph’, J. Combin. Theory Ser. B 19(2) (1975), 161–173. Google Scholar | DOI

[16] Gerencsér, L. and Gyárfás, A., ‘On ramsey-type problems’, Ann. Univ. Sci. Budapest. Eötvös Sect. Math 10 (1967), 167–170. Google Scholar

[17] Gyárfás, A. and Lehel, J., ‘A Ramsey-type problem in directed and bipartite graphs’, Periodica Mathematica Hungarica 3(3–4) (1973), 299–304. Google Scholar | DOI

[18] Hrbacek, K. and Jech, T., Introduction to Set Theory, third edn. (Marcel Dekker, Inc., New York, 1999). Google Scholar

[19] Komjáth, P. and Totik, V., Problems and Theorems in Classical Set Theory (Springer Science & Business Media, New York, 2006). Google Scholar

[20] König, D., ‘Über eine schlussweise aus dem endlichen ins unendliche’, Acta Sci. Math. (Szeged) 3(2–3) (1927), 121–130. Google Scholar

[21] Lamaison, A., ‘Ramsey upper density of infinite graphs’, Combinatorics, Probability and Computing 32(5) (2023), 703–723. Google Scholar | DOI

[22] Lambie-Hanson, C., Personal communication. Google Scholar

[23] Lee, C., ‘Ramsey numbers of degenerate graphs’, Ann. of Math. (2) 185(3) (2017), 791–829. Google Scholar | DOI

[24] Lehner, F., ‘When is it true that if is isomorphic to a spanning subgraph of and vice versa, then is isomorphic to ?’, MathOverflow, URL: https://mathoverflow.net/q/368025 (version: 2020-07-31). Google Scholar

[25] Lo, A., Sanhueza-Matamala, N. and Wang, G., ‘Density of monochromatic infinite paths’, Electron. J. Combin. 25(4) (2018), Paper 4.29. Google Scholar | DOI

[26] Pokrovskiy, A., ‘Partitioning edge-coloured complete graphs into monochromatic cycles and paths’, J. Combin. Theory Ser. B 106 (2014), 70–97. Google Scholar | DOI

[27] Rado, R., ‘Monochromatic paths in graphs’, Ann. Discrete Math. 3 (1978), 191–194, Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). Google Scholar

[28] Ramsey, F. P., ‘On a problem of formal logic’, Proc. London Math. Soc. (2) 30(4) (1929), 264–286. Google Scholar

[29] Soukup, D. T., ‘Colouring problems of Erdős and Rado on infinite graphs’, PhD thesis (2015), University of Toronto (Canada). Google Scholar

[30] Yu, P. and Li, Y., ‘All Ramsey numbers for brooms in graphs’, Electron. J. Combin. 23(3) (2016), Paper P3.29. Google Scholar | DOI

[31] Zhao, Y., ‘Proof of the Conjecture for large ’, Electron. J. Combin. 18(1) (2011), Paper P27. Google Scholar

Cité par Sources :