Effective bounds for induced size-Ramsey numbers of cycles

EUROCOMB’23

Domagoj Bradac Nemanja Draganic Benny Sudakov

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-027

PDF
Abstract
The induced size-Ramsey number $\hat{r}_\text{ind}^k(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have such that for any $k$-coloring of its edges, there exists a monochromatic copy of $H$ which is an induced subgraph of $G$. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $\hat{r}_\text{ind}^k(C_n)\leq Cn$ for some $C=C(k)$. The constant $C$ comes from the use of the regularity lemma, and has a tower type dependence on $k$. In this paper we significantly improve these bounds, showing that $\hat{r}_\text{ind}^k(C_n)\leq O(k^{102})n$ when $n$ is even, thus obtaining only a polynomial dependence of $C$ on $k$. We also prove $\hat{r}_\text{ind}^k(C_n)\leq e^{O(k\log k)}n$ for odd $n$, which almost matches the lower bound of $e^{\Omega(k)}n$. Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $\hat{r}^k(C_n)=e^{O(k)}n$ for odd $n$. This substantially improves the best previous result of $e^{O(k^2)}n$, and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.

Pages:
193–200
References

Noga Alon. Explicit Ramsey graphs and orthonormal labelings. The Electronic Journal of Combinatorics, pages R12-R12, 1994.
https://doi.org/10.37236/1192

József Beck. On size Ramsey number of paths, trees, and circuits. I. Journal of Graph Theory, 7(1):115-129, 1983.
https://doi.org/10.1002/jgt.3190070115

D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory. In: Surveys in Combinatorics 2015, Cambridge University Press, 2015, 49-118.
https://doi.org/10.1017/CBO9781316106853.003

W. Deuber, A generalization of Ramsey's theorem. In: Infinite and Finite Sets, Vol.1, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland, Amsterdam/London, 1975, 323-332.

Nemanja Draganić, Stefan Glock, and Michael Krivelevich. Short proofs for long induced paths. Combinatorics, Probability and Computing, 31(5):870-878, 2022.
https://doi.org/10.1017/S0963548322000013

Nemanja Draganić, Michael Krivelevich, and Rajko Nenadov. Rolling backwards can move you forward: on embedding problems in sparse expanders. Transactions of the American Mathematical Society, 2022.
https://doi.org/10.1090/tran/8660

Nemanja Draganić and Kalina Petrova. Size-Ramsey numbers of graphs with maximum degree three. arXiv preprint arXiv:2207.05048, 2022.

Andrzej Dudek and Paweł Prałat. An alternative proof of the linearity of the size-Ramsey number of paths. Combinatorics, Probability and Computing, 24(3):551-555, 2015.
https://doi.org/10.1017/S096354831400056X

Andrzej Dudek and Paweł Prałat. On some multicolor Ramsey properties of random graphs. SIAM Journal on Discrete Mathematics, 31(3):2079-2092, 2017.
https://doi.org/10.1137/16M1069717

Paul Erdős. Problems and results on finite and infinite graphs. In Recent Advances in Graph Theory. Proceedings of the Second Czechoslovak Symposium, pages 183-192. Academia, Prague, 1975.

Paul Erdős, Ralph J. Faudree, Cecil C. Rousseau, and Richard H. Schelp. The size Ramsey number. Periodica Mathematica Hungarica, 9(1-2):145-161, 1978.
https://doi.org/10.1007/BF02018930

P. Erdős, A. Hajnal, and L. Pósa. Strong embeddings of graphs into colored graphs. In: Infinite and Finite Sets, Vol. 1, Colloquia Mathematica Societatis János Bolyai, Vol. 10, North-Holland, Amsterdam/London, 1975, 585-595.

Jacob Fox and Benny Sudakov. Induced Ramsey-type theorems. Advances in Mathematics, 219(6):1771-1800, 2008.
https://doi.org/10.1016/j.aim.2008.07.009

Joel Friedman and Nicholas Pippenger. Expanding graphs contain all small trees. Combinatorica, 7(1):71-76, 1987.
https://doi.org/10.1007/BF02579202

Penny E. Haxell, Yoshiharu Kohayakawa, and Tomasz Łuczak. The induced size-Ramsey number of cycles. Combinatorics, Probability and Computing, 4(3):217-239, 1995.
https://doi.org/10.1017/S0963548300001619

Ramin Javadi, Farideh Khoeini, Gholam Reza Omidi, and Alexey Pokrovskiy. On the size-Ramsey number of cycles. Combinatorics, Probability and Computing, 28(6):871-880, 2019.
https://doi.org/10.1017/S0963548319000221

Ramin Javadi and Meysam Miralaei. The multicolor size-Ramsey numbers of cycles. Journal of Combinatorial Theory, Series B, 158:264-285, 2023.
https://doi.org/10.1016/j.jctb.2022.10.003

Nina Kamčev, Anita Liebenau, David R. Wood, and Liana Yepremyan. The size Ramsey number of graphs with bounded treewidth. SIAM Journal on Discrete Mathematics, 35(1):281-293, 2021.
https://doi.org/10.1137/20M1335790

Yoshiharu Kohayakawa, Hans Jürgen Promel, and Vojtěch Rödl. Induced Ramsey numbers. Combinatorica, 18(3):373-404, 1998.
https://doi.org/10.1007/PL00009828

Yoshiharu Kohayakawa, Vojtěch Rödl, Mathias Schacht, and Endre Szemerédi. Sparse partition universal graphs for graphs of bounded degree. Advances in Mathematics, 226(6):5041-5065, 2011.
https://doi.org/10.1016/j.aim.2011.01.004

Michael Krivelevich. Expanders-how to find them, and what to find in them. In: Surveys in combinatorics 2019, volume 456 of London Mathematical Society Lecture Note Series, pages 115-142. Cambridge University Press, Cambridge, 2019.
https://doi.org/10.1017/9781108649094.005

Michael Krivelevich. Long cycles in locally expanding graphs, with applications. Combinatorica, 39(1):135-151, 2019.
https://doi.org/10.1007/s00493-017-3701-1

Frank P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30(4):264-286, 1929.
https://doi.org/10.1112/plms/s2-30.1.264

Vojtěch Rödl. The dimension of a graph and generalized Ramsey theorems, Master's thesis, Charles University, 1973.

Vojtěch Rödl and Endre Szemerédi. On size Ramsey numbers of graphs with bounded degree. Combinatorica, 20(2):257-262, 2000.
https://doi.org/10.1007/s004930070024

Konstantin Tikhomirov. On bounded degree graphs with large size-Ramsey numbers. arXiv preprint arXiv:2210.05818, 2022.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Domagoj Bradac, Nemanja Draganic, Benny Sudakov

PDF