Ramsey numbers for degree monotone paths

A path v1,v2,…,vmv1,v2,…,vm in a graph GG is degree-monotone   if deg(v1)≤deg(v2)≤⋯≤deg(vm)deg(v1)≤deg(v2)≤⋯≤deg(vm) where deg(vi)deg(vi) is the degree of vivi in GG. Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by Mk(m)Mk(m) the minimum number MM such that for all n≥Mn≥M, in any kk-edge coloring of KnKn there is some 1≤j≤k1≤j≤k such that the graph formed by the edges colored jj has a degree-monotone path of order mm. We prove several nontrivial upper and lower bounds for Mk(m)Mk(m).