episciences.org_4372_1642976581
1642976581
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
1365-8050
10
02
2019
vol. 21 no. 4
Graph Theory
Monochromatic loose paths in multicolored $k$-uniform cliques
Andrzej
Dudek
Andrzej
RuciĆski
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=\emptyset$ if $|i-j|\ge2$. 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\ge3$, $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 $cn^k$. We also
prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.
10
02
2019
4372
arXiv:1803.05051
10.23638/DMTCS-21-4-7
https://dmtcs.episciences.org/4372