While trying to characterize constraint satisfaction problems which can be solved by the Linear Programming relaxation, I've run into a few perplexing puzzles related to the existence of certain ordered combinatorial designs. One of these puzzles led me to the following question about approximate colorings of the Kneser graph:

> Let $K(4k,k)$ be the [Kneser graph][1] consisting of all $k$-element subsets of a $4k$-element set, with an edge connecting every pair of disjoint subsets. If $k$ is large enough, is it possible to color the vertices of $K(4k,k)$ with $4$ colors so that at least a $1 - \epsilon$ fraction of the edges of $K(4k,k)$ connect vertices with different colors, for any fixed $\epsilon > 0$?

Unfortunately, almost all of the research I've been able to find about the Kneser graph has focused on proving that certain subgraphs of it have *large* chromatic number, such as the paper [**On random subgraphs of Kneser and Schrijver graphs**](https://doi.org/10.1016/j.jcta.2016.02.003), which proves that random subgraphs of the Kneser graph have a similar chromatic number to the whole thing.

I should note that what I am asking for above is much stronger than what I actually need for the application I have in mind: all I really need is a collection of $24$ *orientations* of the Kneser graph $K(4k,k)$ such that for all but a $1-\epsilon$ fraction of the $4$-cliques of $K(4k,k)$, the restriction of these $24$ orientations to the clique is a list of all $24$ transitive tournaments on the $4$ vertices, each occurring exactly once. If I had an approximate $4$-coloring, then I could immediately produce such a family of orientations by simply ordering the $4$ color classes in all $24$ possible ways.

  [1]: https://en.wikipedia.org/wiki/Kneser_graph