Induced Ramsey problems for trees and graphs with bounded treewidth

Hunter, Zach; Sudakov, Benny

doi:10.1090/proc/17243

Induced Ramsey problems for trees and graphs with bounded treewidth
HTML articles powered by AMS MathViewer

by Zach Hunter and Benny Sudakov;

Proc. Amer. Math. Soc.

DOI: https://doi.org/10.1090/proc/17243

Published electronically: June 27, 2025

PDF | Request permission

Abstract:

The induced $q$-color size-Ramsey number $\hat {r}_{\mathrm {ind}}(H;q)$ of a graph $H$ is the minimal number of edges a host graph $G$ can have so that every $q$-edge-coloring of $G$ contains a monochromatic copy of $H$ which is an induced subgraph of $G$. A natural question, which in the non-induced case has a very long history, asks which families of graphs $H$ have induced Ramsey numbers that are linear in $|H|$. We prove that for every $k,w,q$, if $H$ is an $n$-vertex graph with maximum degree $k$ and treewidth at most $w$, then $\hat {r}_{\mathrm {ind}}(H;q) = O_{k,w,q}(n)$. This extends several old and recent results in Ramsey theory. Our proof is quite simple and relies upon a novel reduction argument.

References

Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
József Beck, On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory 7 (1983), no. 1, 115–129. MR 693028, DOI 10.1002/jgt.3190070115
József Beck, On size Ramsey number of paths, trees and circuits. II, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 34–45. MR 1083592, DOI 10.1007/978-3-642-72905-8_{4}
Sören Berger, Yoshiharu Kohayakawa, Giulia Satiko Maesaka, Taísa Martins, Walner Mendonça, Guilherme Oliveira Mota, and Olaf Parczyk, The size-Ramsey number of powers of bounded degree trees, J. Lond. Math. Soc. (2) 103 (2021), no. 4, 1314–1332. MR 4273470, DOI 10.1112/jlms.12408
Domagoj Bradač, Nemanja Draganić, and Benny Sudakov, Effective bounds for induced size-Ramsey numbers of cycles, Combinatorica 44 (2024), no. 5, 1011–1039. MR 4805886, DOI 10.1007/s00493-024-00103-5
David Conlon, Jacob Fox, and Benny Sudakov, On two problems in graph Ramsey theory, Combinatorica 32 (2012), no. 5, 513–535. MR 3004807, DOI 10.1007/s00493-012-2710-3
David Conlon, Jacob Fox, and Benny Sudakov, Recent developments in graph Ramsey theory, Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 49–118. MR 3497267
David Conlon, Rajko Nenadov, and Miloš Trujić, On the size-Ramsey number of grids, Combin. Probab. Comput. 32 (2023), no. 6, 874–880. MR 4653728, DOI 10.1017/s0963548323000147
Dennis Clemens, Matthew Jenssen, Yoshiharu Kohayakawa, Natasha Morrison, Guilherme Oliveira Mota, Damian Reding, and Barnaby Roberts, The size-Ramsey number of powers of paths, J. Graph Theory 91 (2019), no. 3, 290–299. MR 3957380, DOI 10.1002/jgt.22432
W. Deuber, Generalizations of Ramsey’s theorem, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam-London, 1975, pp. 323–332. MR 369127
Nemanja Draganić, Stefan Glock, and Michael Krivelevich, Short proofs for long induced paths, Combin. Probab. Comput. 31 (2022), no. 5, 870–878. MR 4472292, DOI 10.1017/s0963548322000013
N. Draganić, M. Kaufmann, D. Munhá Correia, K. Petrova, and R. Steiner, Size-Ramsey numbers of structurally sparse graphs, arXiv:2307.12028, 2023.
P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978), no. 1-2, 145–161. MR 479691, DOI 10.1007/BF02018930
P. Erdős, A. Hajnal, and L. Pósa, Strong embeddings of graphs into colored graphs, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam-London, 1975, pp. 585–595. MR 382049
Paul Erdős, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 183–192. (loose errata). MR 389669
P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), no. 1, 25–42. MR 602413, DOI 10.1007/BF02579174
Jacob Fox and Benny Sudakov, Induced Ramsey-type theorems, Adv. Math. 219 (2008), no. 6, 1771–1800. MR 2455625, DOI 10.1016/j.aim.2008.07.009
Jacob Fox and Benny Sudakov, Dependent random choice, Random Structures Algorithms 38 (2011), no. 1-2, 68–99. MR 2768884, DOI 10.1002/rsa.20344
J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71–76. MR 905153, DOI 10.1007/BF02579202
A. Girão and E. Hurley, Embedding induced trees in sparse expanding graphs, manuscript.
Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995
Jie Han, Matthew Jenssen, Yoshiharu Kohayakawa, Guilherme Oliveira Mota, and Barnaby Roberts, The multicolour size-Ramsey number of powers of paths, J. Combin. Theory Ser. B 145 (2020), 359–375. MR 4117868, DOI 10.1016/j.jctb.2020.06.004
P. E. Haxell and Y. Kohayakawa, The size-Ramsey number of trees, Israel J. Math. 89 (1995), no. 1-3, 261–274. MR 1324465, DOI 10.1007/BF02808204
P. E. Haxell, Y. Kohayakawa, and T. Łuczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995), no. 3, 217–239. MR 1356576, DOI 10.1017/S0963548300001619
Z. Hunter and B. Sudakov, Induced Ramsey problems for trees and graphs with bounded treewidth, arXiv:2406.00352 (2024).
Tao Jiang, Kevin G. Milans, and Douglas B. West, Degree Ramsey numbers for cycles and blowups of trees, European J. Combin. 34 (2013), no. 2, 414–423. MR 2994408, DOI 10.1016/j.ejc.2012.08.004
Nina Kamcev, Anita Liebenau, David R. Wood, and Liana Yepremyan, The size Ramsey number of graphs with bounded treewidth, SIAM J. Discrete Math. 35 (2021), no. 1, 281–293. MR 4223216, DOI 10.1137/20M1335790
M. Krivelevich and B. Sudakov, Pseudo-random graphs, More sets, graphs and numbers, Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 2006, pp. 199–262. MR 2223394, DOI 10.1007/978-3-540-32439-3_{1}0
Yuejian Peng, Vojtech Rödl, and Andrzej Ruciński, Holes in graphs, Electron. J. Combin. 9 (2002), no. 1, Research Paper 1, 18. MR 1887082, DOI 10.37236/1618
V. Rödl, The dimension of a graph and generalized Ramsey theorems, Master’s thesis, Charles University, 1973.

AMS Website Down

Proceedings of the American Mathematical Society

Induced Ramsey problems for trees and graphs with bounded treewidth
HTML articles powered by AMS MathViewer

Abstract: