Directed Kneser graph existence for b-tuple colourings

AX_directed_kneser_graphs_existence

Source: arXiv:1812.02420 — On the Complexity of Digraph Colourings and Vertex Arboricity

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 ai-disproved high confidence

For positive integers, such a digraph exists exactly when b is at most 2 or k is at most b+1; in particular, (k,b)=(5,3) is impossible.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

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