Domagoj Bradač, Effective bounds for induced size-Ramsey numbers of cycles

The k-color induced size-Ramsey number 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., for some C=C(k), there is a graph with at most Cn edges whose any k-edge-coloring contains a monochromatic induced cycle of length n. The value of C comes from the use of the sparse regularity lemma and has a tower-type dependence on k. In this work, we obtain nearly optimal bounds for the required value of C. Joint work with Nemanja Draganić and Benny Sudakov.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.