Monochromatic loose paths in multicolored $k$-uniform cliques

Abstract

For integers $k\ge 2$ and $\ell \ge 0$, a $k$-uniform hypergraph is called a loose path of length $\ell$, and denoted by $P_{\ell }^{(k)}$, if it consists of $\ell$ edges $e_1,\dots ,e_{\ell }$ such that $|e_i\cap e_j|=1$ if $|i-j|=1$ and $e_i\cap e_j=\varnothing$ if $|i-j|\ge 2$. In other words, each pair of consecutive edges intersects on a single vertex, while all other pairs are disjoint. Let $R(P_{\ell }^{(k)};r)$ be the minimum integer $n$ such that every $r$-edge-coloring of the complete $k$-uniform hypergraph $K_n^{(k)}$ yields a monochromatic copy of $P_{\ell }^{(k)}$. In this paper we are mostly interested in constructive upper bounds on $R(P_{\ell }^{(k)};r)$, meaning that on the cost of possibly enlarging the order of the complete hypergraph, we would like to efficiently find a monochromatic copy of $P_{\ell }^{(k)}$ in every coloring. In particular, we show that there is a constant $c>0$ such that for all $k\ge 2$, $\ell \ge 3$, $2\le r\le k-1$, and $n\ge k(\ell +1)r(1+\ln (r))$, there is an algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it finds a monochromatic copy of $P_{\ell }^{(k)}$ in time at most $c{n}^k$. We also prove a non-constructive upper bound $R(P_{\ell }^{(k)};r)\le (k-1)\ell r$.

References in corpus (2)

• An alternative proof of the linearity of the size-Ramsey number of paths
• Multicolour Ramsey numbers of paths and even cycles