Directed Kneser graph existence for b-tuple colourings

Problem 5.40 · arXiv:1812.02420

arXiv Problem high confidence— first stated 2020-01-09

Authors: Winfried Hochstättler, Felix Schröder, Raphael Steiner

Status open high confidence

No paper has been found that constructs the directed Kneser graphs $\vec{K}(k,b)$ of Problem 5.40 for general $k\geq b$, or refutes their existence. Related work studies the dichromatic number of Kneser-type digraphs (arXiv:2309.16565, arXiv:2511.12553) and develops circular homomorphism theory, but none directly resolves whether the intersection-acyclicity equivalence required by Problem 5.40 can be achieved. The only confirmed case ($k=b+1$, the directed $(b+1)$-cycle) remains as stated in the source paper.

Reviewer notes. Search surfaced two related papers: arXiv:2309.16565 ('Colouring Complete Multipartite and Kneser-type Digraphs', 2023) studies dichromatic numbers of Kneser digraphs with canonical orientations; arXiv:2511.12553 ('On the Dichromatic Number of Generalized Kneser and Johnson Digraphs', 2025) extends this to generalized Kneser and Johnson digraphs. Neither addresses the specific intersection-acyclicity construction of Problem 5.40. No follow-up resolving the problem was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. For given $k,b\in\mathbb{N}$ with $k\geq b$, is there a directed graph $\vec{K}(k,b)$ with vertex set $\binom{[k]}{b}$ such that the following holds? The subdigraph of $\vec{K}(k,b)$ induced by any $\{B_{1},\ldots,B_{l}\}\subseteq\binom{[k]}{b}$ is acylic if and only if $\bigcap_{i=1}^{l}{B_{i}}\neq\emptyset$.

Context

Such 'directed Kneser graphs' $\vec{K}(k,b)$ would allow $b$-tuple $k$-colourings of digraphs to be equivalent to the existence of circular homomorphisms to $\vec{K}(k,b)$, tying the fractional dichromatic number to circular homomorphism theory. Existence is confirmed for $k=b+1$ via the directed cycle of length $b+1$, but the general case is open.

Source paper

On the Complexity of Digraph Colourings and Vertex Arboricity
Winfried Hochstättler, Felix Schröder, Raphael Steiner · 2020-01-09
https://arxiv.org/abs/1812.02420