The multicolor induced size-Ramsey number of long subdivisions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910062363017216 |
|---|---|
| author | Javadi, Ramin Kohayakawa, Yoshiharu Miralaei, Meysam |
| author_facet | Javadi, Ramin Kohayakawa, Yoshiharu Miralaei, Meysam |
| contents | For a positive integer $k$ and a graph $H$, the $k$-color induced size-Ramsey number $\hat{R}_{\mathrm{ind}}(H, k)$ is the minimum integer $m$ for which there exists a graph $G$ with $m$ edges such that for every $k$-edge coloring of $G$, the graph $G$ contains a monochromatic copy of $H$ as an induced subgraph. For a graph $H$ with the edge set $E(H)$ and a function $σ:E(H)\to \mathbb{N}$, the subdivision $H^σ$ is obtained by replacing each $e \in E(H)$ with a path of length $σ(e)$. We prove that for all integers $k,\, D\geq 2$, there exists a constant $c=c(k, D)$ such that the following holds. Let $ H $ be any graph with maximum degree $D$ and let $H^σ$ be a subdivision of $H$ with $σ(e) > c \log_D n $ for every $e \in E(H)$, where $n$ is the order of $H^σ$. Then, $\hat{R}_{\mathrm{ind}}(H^σ,k)=e^{O(k\log k)} D^{9}(\log D)\, n$. If each $σ(e)$ is even and larger than $c \log_D n$, this bound improves to $\hat{R}_{\mathrm{ind}}(H^σ,k)=O(k^{342} (\log k)^9D^{9} \log D )n$. We also find improved bounds for the non-induced size-Ramsey number of long subdivisions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_05960 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The multicolor induced size-Ramsey number of long subdivisions Javadi, Ramin Kohayakawa, Yoshiharu Miralaei, Meysam Combinatorics 05D10, 05C55 For a positive integer $k$ and a graph $H$, the $k$-color induced size-Ramsey number $\hat{R}_{\mathrm{ind}}(H, k)$ is the minimum integer $m$ for which there exists a graph $G$ with $m$ edges such that for every $k$-edge coloring of $G$, the graph $G$ contains a monochromatic copy of $H$ as an induced subgraph. For a graph $H$ with the edge set $E(H)$ and a function $σ:E(H)\to \mathbb{N}$, the subdivision $H^σ$ is obtained by replacing each $e \in E(H)$ with a path of length $σ(e)$. We prove that for all integers $k,\, D\geq 2$, there exists a constant $c=c(k, D)$ such that the following holds. Let $ H $ be any graph with maximum degree $D$ and let $H^σ$ be a subdivision of $H$ with $σ(e) > c \log_D n $ for every $e \in E(H)$, where $n$ is the order of $H^σ$. Then, $\hat{R}_{\mathrm{ind}}(H^σ,k)=e^{O(k\log k)} D^{9}(\log D)\, n$. If each $σ(e)$ is even and larger than $c \log_D n$, this bound improves to $\hat{R}_{\mathrm{ind}}(H^σ,k)=O(k^{342} (\log k)^9D^{9} \log D )n$. We also find improved bounds for the non-induced size-Ramsey number of long subdivisions. |
| title | The multicolor induced size-Ramsey number of long subdivisions |
| topic | Combinatorics 05D10, 05C55 |
| url | https://arxiv.org/abs/2602.05960 |