Exponential induced size-Ramsey conjecture for odd cycles

Let CnC_n be the cycle on nn vertices, and let r^indk(Cn)\hat{r}^k_{\operatorname{ind}}(C_n) denote the smallest number of edges in a graph whose every kk-coloring contains a monochromatic copy of CnC_n as an induced subgraph. Exponential induced-cycle conjecture. For odd nn,

r^indk(Cn)eO(k)n.\hat{r}^k_{\operatorname{ind}}(C_n)\leq e^{O(k)}n.

The paper proves the weaker bound r^indk(Cn)eO(klogk)n\hat{r}^k_{\operatorname{ind}}(C_n)\leq e^{O(k\log k)}n for odd cycles, so the conjectured exponential dependence on kk remains open.

Sources & referencesView supporting material

Primary source

Domagoj Bradač, Nemanja Draganić and Benny Sudakov, “Effective bounds for induced size-Ramsey numbers of cycles”, arXiv:2301.10160 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.