Bounded colorings of multipartite graphs and hypergraphs

We also study multipartite analogues of these questions. We give (up to a constant factor) optimal sufficient conditions for a coloring c of the complete balanced m-partite graph to contain a properly colored or rainbow copy of a given graph G with maximum degree Δ. Our bounds exhibit a surprising transition in the rate of growth, showing that the problem is fundamentally different in the regimes Δ≫m and Δ≪m. Our main tool is the framework of Lu and Székely for the space of random bijections, which we extend to product spaces.