Near-acyclic r-free digraphs for r > 2n/3

Conjecture on r-free digraphs with r > 2n/3 · arXiv:2204.01938

arXiv Informal medium confidence— first stated 2022-04-19

Authors: Jacob Fox, Zoe Himwich, Nitya Mani

Status solved medium confidence

A January 2026 MIT PRIMES research paper by Kai Lum (mentored by Nitya Mani, one of the conjecture's authors) proves that β(G) ≤ 1 for all r-free digraphs on n vertices with r > ⌊2n/3⌋, directly resolving the conjecture. The source paper (arXiv:2204.01938) was subsequently published in Random Structures & Algorithms (2024). No peer-reviewed journal or arXiv paper proving this conjecture was found; the only identified proof is in an unreviewed PRIMES preprint whose PDF could not be fully read, hence medium confidence.

Cited literature (1)

proof Extremal Structural Results for Feedback Arc Sets and Graph Inversions (2026)

Kai Lum · MIT PRIMES Research Paper (preprint, not peer-reviewed)

Proves that β(G) ≤ 1 for all r-free digraphs on n vertices with r > ⌊2n/3⌋, as well as β(G) ≤ 2 for r > n/2 under an additional forbidden-structure condition; the work is mentored by Nitya Mani, a co-author of the original conjecture.

Reviewer notes. The Lum PRIMES paper (posted January 2026, PDF available at the MIT PRIMES site) was indexed by search engines with text indicating it proves β(G) ≤ 1 when r > ⌊2n/3⌋; the mentor Nitya Mani is a co-author of the source paper, lending credibility to this claim. However, the PDF was unreadable via WebFetch (binary), and the paper is not peer-reviewed, so confidence is medium rather than high. The source paper itself appeared in Random Structures & Algorithms in 2024 (DOI: 10.1002/rsa.21179, behind paywall). The arXiv paper 2511.22562 (Bang-Jensen et al., 2025) on making oriented graphs acyclic via inversions does not address this conjecture.

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

Informal. All $r$-free digraphs on $n$ vertices with $r > 2n/3$ are at most one edge away from being acyclic.

Context

The authors first construct a family of $r$-free digraphs $G$ on $n$ vertices with $\beta(G) \geq n^2/(r+1)^2$, implying that if every $r$-free digraph satisfies $\beta(G) = O(1)$ then $r = \Omega(n)$. In the converse direction they pose this conjecture, noting tightness: for $n$ a multiple of $3$ there exists an $(r-1)$-free digraph $G$ on $n$ vertices with $r = 2n/3$ and $\beta(G) = 2$.

Notes. Stated in running prose with explicit 'we conjecture' language; no labelled theorem environment.

Source paper

Extremal results on feedback arc sets in digraphs
Jacob Fox, Zoe Himwich, Nitya Mani · 2022-04-19
https://arxiv.org/abs/2204.01938 PDF source