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

Less than 1 year old · traced to

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)) n2mlog⁡2mn.\vec{\alpha}(D) \geq (1+o(1))\,\frac{n^2}{m} \log_2 \frac{m}{n}.

For tournaments this predicts α⃗(D)≥(2+o(1))log⁡2n\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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.