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 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 $5$ 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$?
I'm also interested in the answer to the same question with the number $5$ replaced with any other fixed number.
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, 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 (say) $120$ 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 $120$ orientations to the clique is a list of all $24$ transitive tournaments on the $4$ vertices, each occurring exactly $5$ times. If I had an approximate $5$-coloring, then I could immediately produce such a family of orientations by simply ordering the $5$ color classes in all $120$ possible ways.
