On the size-Ramsey number of tight paths

Abstract

For any $r\ge 2$ and $k\ge 3$, the $r$-color size-Ramsey number $\hat{R}(\mathcal{G},r)$ of a $k$-uniform hypergraph $\mathcal{G}$ is the smallest integer $m$ such that there exists a $k$-uniform hypergraph $\mathcal{H}$ on $m$ edges such that any coloring of the edges of $\mathcal{H}$ with $r$ colors yields a monochromatic copy of $\mathcal{G}$. Let ${\mathcal{P}}_{n,k-1}^{(k)}$ denote the $k$-uniform tight path on $n$ vertices. Dudek, Fleur, Mubayi and Rődl showed that the size-Ramsey number of tight paths $\hat{R}({\mathcal{P}}_{n,k-1}^{(k)},2)=O(n^{k-1-\alpha }(\log n{)}^{1+\alpha })$ where $\alpha =\frac{k-2}{\left(\genfrac{}{}{0ex}{}{k-1}{2}\right)+1}$. In this paper, we improve their bound by showing that $\hat{R}({\mathcal{P}}_{n,k-1}^{(k)},r)=O(r^k(n\log n{)}^{k/2})$ for all $k\ge 3$ and $r\ge 2$.

9 pages

References in corpus (1)

• Path Ramsey number for random graphs