Monochromatic loose paths in multicolored k-uniform cliques

From MaRDI portal
(Redirected from Monochromatic loose paths in multicolored k-uniform cliques)
Monochromatic loose paths in multicolored $k$-uniform cliques



Abstract: For integers kge2 and ellge0, a k-uniform hypergraph is called a loose path of length ell, and denoted by Pell(k), if it consists of ell edges e1,dots,eell such that |eicapej|=1 if |i−j|=1 and eicapej=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(Pell(k);r) be the minimum integer n such that every r-edge-coloring of the complete k-uniform hypergraph Kn(k) yields a monochromatic copy of Pell(k). In this paper we are mostly interested in constructive upper bounds on R(Pell(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 Pell(k) in every coloring. In particular, we show that there is a constant c>0 such that for all kge2, ellge3, 2lerlek−1, and ngek(ell+1)r(1+ln(r)), there is an algorithm such that for every r-edge-coloring of the edges of Kn(k), it finds a monochromatic copy of Pell(k) in time at most cnk. We also prove a non-constructive upper bound R(Pell(k);r)le(k−1)ellr.












This page was built for publication: Monochromatic loose paths in multicolored $k$-uniform cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207843)