Local edge budgets for Thomassé's nonneighbor conjecture

Definitions and mathematical statement

Let $D=(V,E)$ be a nonempty finite simple digraph on $n$ vertices having no directed cycle of length one, two, or three. In particular, it has no loops or opposite arcs. For $v\in V$, define its non-neighbours by \[ Z(v)=\{w\in V\setminus\{v\}:v\to w\notin E \text{ and }w\to v\notin E\}. \] Thus a non-neighbour has no adjacency to $v$ in either direction. Let $d^+(v)$ and $d^-(v)$ count its outgoing and incoming neighbours. The three sets of outgoing neighbours, incoming neighbours, and non-neighbours partition $V\setminus\{v\}$.

Thomassé's conjecture is that some vertex satisfies \[ d^+(v)\le |Z(v)|. \] Equivalently, there exists $v$ with $2d^+(v)+d^-(v)\le n-1$. The exclusion of directed triangles concerns cyclic orientations; transitive triangles are allowed. The statement makes no bound on the size of the digraph and does not assume that its degrees are balanced or that it is strongly connected. A sink automatically provides a witness, but the question applies also to graphs with positive minimum outdegree. The non-neighbour count excludes the vertex itself. The simplicity convention is necessary when degree means number of arcs: repeated parallel arcs could increase the outdegree without changing the non-neighbours or creating a short cycle.

Short English statement

Does every directed graph without a cycle of length at most three have a vertex with no more outgoing neighbours than non-neighbours?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20001055 (AIM-COMBINATORICS-0180), 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-0180. https://aimath.org/WWN/caccetta/caccetta.pdf.