Kostochka–Stiebitz gap conjecture for oriented dicritical digraphs

About 4 years old · traced to

Let dk(n)d_k(n) be the minimum number of arcs in a kk-dicritical digraph of order nn, and let ok(n)o_k(n) be the minimum number of arcs in a kk-dicritical oriented graph of order nn, with value +∞+\infty when no such oriented graph exists. Kostochka–Stiebitz gap conjecture. There exists ε>0\varepsilon>0 such that

ok(n)≥(1+ε)⋅dk(n)o_k(n)\geq(1+\varepsilon)\cdot d_k(n)

for every k≥4k\geq4 and sufficiently large nn. The conjecture asserts a uniform asymptotic density gap between arbitrary and oriented kk-dicritical digraphs; the source notes that it is known for k=3k=3 and k=4k=4, but remains open for general kk.

References

Primary source

Frédéric Havet, Florian Hörsch and Lucas Picasarri-Arrieta, “The 3-dicritical semi-complete digraphs”, arXiv:2402.12014 (2024).

Additional references

4 papers in this index state this conjecture (2022–2024). The statement above is taken from the most recent of them; the others are arXiv:2310.03584, arXiv:2306.10784, arXiv:2207.01051.

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.