LP obstructions and cyclic blow-ups for DeVos's distribution conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite nonempty directed graph with no directed cycles of lengths one, two, or three. Parallel arcs can be discarded, since only reachability and vertex sets occur below. For each vertex $v$, let \[ N^+(v)=\{w:v\to w\},\qquad N^-(v)=\{w:w\to v\}, \] and let $N^-_2(v)$ be the vertices whose shortest directed path to $v$ has length exactly two. In particular, $N^-_2(v)$ excludes $v$ and all its immediate in-neighbors, even when a two-step walk also exists. For a probability vector $p:V\to[0,1]$ with $\sum_{v\in V}p(v)=1$, put $p(S)=\sum_{s\in S}p(s)$.

DeVos's question asks whether every such graph admits a single probability vector satisfying simultaneously, at every vertex $v$, \[ p(N^+(v))\geq p(N^-(v)),\qquad p(N^-_2(v))\geq p(N^-(v)). \] The weights are attached to vertices, may be zero, and are not required to be equal. The same distribution must work for all inequalities; selecting a different distribution for each vertex would weaken the problem. The formulation is a feasibility assertion for a finite system of linear inequalities determined by the graph. In particular, it asks for vertexwise inequalities, rather than merely an averaged inequality after summing over $v$. No assumption of strong connectivity or positive minimum degree is imposed, so sources and sinks are included in the universal quantifier.

Short English statement

Does every digraph without directed triangles or shorter cycles have a probability distribution satisfying both prescribed neighborhood inequalities at every vertex?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001073 (AIM-COMBINATORICS-0198), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, The Caccetta-Haggkvist conjecture, item 6. Original workshop question underlying AIM-COMBINATORICS-0198. https://aimath.org/WWN/caccetta/caccetta.pdf.