The Multicolor Size-Ramsey Number of Bipartite Long Subdivisions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910032619110400 |
|---|---|
| author | Javadi, Ramin Kohayakawa, Yoshiharu Miralaei, Meysam |
| author_facet | Javadi, Ramin Kohayakawa, Yoshiharu Miralaei, Meysam |
| contents | For a positive integer $r$, the $r$-color size-Ramsey
number~$\widehat{R}_r(H)$ of a graph $H$ is the minimum number of
edges in a graph $G$ such that every $r$-edge coloring of $G$
contains a monochromatic copy of $H$. For a graph~$H$ and a
function $σ:E(H)\to \mathbb{N}$, the \emph{subdivision}
$H^σ$ is obtained by replacing every $e \in E(H)$ with a path
of length $σ(e)$. In~\cite{javadi25:_induced_long} it is shown
that for all integers $r,\, D\geq 2 $, there exists a constant
$c=c(r, D)$ such that for every graph $ H $ with maximum degree $D$
if $H^σ$ is a subdivision of~$H$ in which
$σ(e) > c \log n $ for every $e \in E(H)$, where
$n=|V(H^σ)|$, then
$ \widehat{R}_r(H^σ) = O\big(2^{34r}
r^6 \log^5(r) D^5\log D\big)n. $ We improve upon this result in the case that~$H^σ$
is a bipartite graph and the number of colors~$r$ is large using a
significantly different argument, obtaining the bound
$ \widehat{R}_r(H^σ) \leq r^{400D \log D} \, n $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21453 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Multicolor Size-Ramsey Number of Bipartite Long Subdivisions Javadi, Ramin Kohayakawa, Yoshiharu Miralaei, Meysam Combinatorics For a positive integer $r$, the $r$-color size-Ramsey number~$\widehat{R}_r(H)$ of a graph $H$ is the minimum number of edges in a graph $G$ such that every $r$-edge coloring of $G$ contains a monochromatic copy of $H$. For a graph~$H$ and a function $σ:E(H)\to \mathbb{N}$, the \emph{subdivision} $H^σ$ is obtained by replacing every $e \in E(H)$ with a path of length $σ(e)$. In~\cite{javadi25:_induced_long} it is shown that for all integers $r,\, D\geq 2 $, there exists a constant $c=c(r, D)$ such that for every graph $ H $ with maximum degree $D$ if $H^σ$ is a subdivision of~$H$ in which $σ(e) > c \log n $ for every $e \in E(H)$, where $n=|V(H^σ)|$, then $ \widehat{R}_r(H^σ) = O\big(2^{34r} r^6 \log^5(r) D^5\log D\big)n. $ We improve upon this result in the case that~$H^σ$ is a bipartite graph and the number of colors~$r$ is large using a significantly different argument, obtaining the bound $ \widehat{R}_r(H^σ) \leq r^{400D \log D} \, n $. |
| title | The Multicolor Size-Ramsey Number of Bipartite Long Subdivisions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.21453 |