Asymptotic upper-bound conjecture for the minimum size of k-dicritical oriented graphs

Let ok(n)o_k(n) be the minimum number of arcs in a kk-dicritical oriented graph of order nn. Suppose that, for each fixed kk, there is a constant ckc_k such that

ok(n)=ckn+o(n).o_k(n)=c_k n+o(n).

Asymptotic upper-bound conjecture.

ck2k31when k+.\frac{c_k}{2k-3}\rightarrow 1\quad\text{when }k\rightarrow +\infty.

The paper establishes upper and lower bounds on ok(n)o_k(n) and proposes that the constructions giving the upper bound are nearly optimal, with the asymptotic growth rate approaching the upper bound as kk tends to infinity.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Thomas Bellitto, Frédéric Havet and Clément Rambaud, “On the minimum number of arcs in k-dicritical oriented graphs”, arXiv:2207.01051 (2022).

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.