Defect feedback sets and a fractional obstruction for four-order majority digraphs

Definitions and mathematical statement

Choose four linear orders $<_1,<_2,<_3,<_4$ on a finite nonempty vertex set $V$, with $n=|V|$. Form a digraph $D$ by putting $u\to v$ for distinct $u,v$ exactly when $u<_i v$ in at least three of the four orders. Such a graph is a $3/4$-digraph. It is simple and has no opposite arcs. A two-to-two split produces no edge in either direction. For a vertex $v$, let $d^+(v)$ be its outdegree, and let the girth be the length of a shortest directed cycle when one exists.

The conjecture asks whether every $3/4$-digraph satisfies the Caccetta--Häggkvist bound: for every integer $r\ge1$, if $d^+(v)\ge r$ for all $v$, then there is a directed cycle of length at most $\lceil n/r\rceil$. The four orders are arbitrary and may coincide; the statement is uniform over their choices. These majority digraphs have no directed triangles, since a linear order cannot support all three arcs of a cyclic triangle. Accordingly, a particularly significant consequence would be a vertex of outdegree strictly smaller than $n/3$ in every such graph.

The source also asks about the larger majority classes: given integers $1\le a\le b$ with $a/b>2/3$, use $b$ orders and require agreement in at least $a$ of them. Does the same short-cycle bound hold for these classes as well?

Short English statement

Does the Caccetta–Häggkvist short-cycle bound hold for digraphs defined by agreement of at least three of four linear orders, and for larger majority classes?

Sources

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