I am taking a course in probabilistic methods in combinatorics, and I'm struggling to solve this question:
Prove that for any integer $k$ there is a directed graph (with no parallel edges) in which every outdegree is at least $k$ and yet there is no 2-coloring of the vertex set so that each vertex has at least one outneighbot of each color.
A probabilistic argument would be appreciated, but any clue would help (e.g. an example for such graph for $k=3$ or $k=4$).
I must mention that this question follows a previous question, which I solved, and might serve as a clue; Prove that for any tournament $T=(V,E)$ in which all outdegrees are at least 10, we can color the vertices so that every vertex at least one outneighbor of each color.
There is a simple probability-free argument; on the other hand, I can't think of a way using the probabilistic method (non-trivially) to do it. I would guess that it's just on your assignment because it's related to the previous question.
Here is an example for $k=3$ that's honestly much more complicated than what you really need. (To avoid a messy diagram, I only drew edges down from the top half to the bottom half. Edges from the bottom half can be placed arbitrarily to obtain minimum degree $3$.)
This is a digraph associated to the Fano plane with a vertex for each line and each point, and an edge $\ell \to P$ whenever line $\ell$ contains point $P$. It is a nice trivia fact that in every $2$-coloring of the Fano plane, there is a monochromatic line; therefore, no matter how we color the bottom $7$ vertices (the "points"), one of the top vertices (the "lines") will have all its out-neighbors given the same color.
I think this might be the smallest example for $k=3$, but if you are not attached to minimal examples, there are much simpler approaches along these lines that will solve the problem for all $k$. (If all you want is a $k$-uniform hypergraph that cannot be $2$-colored, with no further constraints, what can you do?)