Aharoni–Berger–Kfir conjecture on acyclic sets in oriented graphs

From papers

Let DD be an oriented graph with nn vertices and mm edges or arcs, and let α(D)\vec{\alpha}(D) denote its largest acyclic set. Aharoni–Berger–Kfir conjecture.

α(D)(1+o(1))n2mlog2mn.\vec{\alpha}(D) \geq (1+o(1))\,\frac{n^2}{m} \log_2 \frac{m}{n}.

For tournaments this predicts α(D)(2+o(1))log2n\vec{\alpha}(D)\geq (2+o(1))\log_2 n; the bound is known up to a factor of 22, and whether this factor can be attained is a major open problem.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Ararat Harutyunyan, Colin McDiarmid and Gil Puig i Surroca, “Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths”, arXiv:2603.02947 (2026).

Solutions 0

No solutions have been posted yet.