Gishboliner–Krivelevich–Michaeli oriented discrepancy conjecture

About 4 years old · traced to

Let GG be an oriented graph on n≥3n\geq 3 vertices, and let δ(G)\delta(G) denote its minimum degree. For a Hamilton cycle CC in GG, let σmax⁡(C)\sigma_{\max}(C) be the larger of the numbers of forward and backward edges of CC. Gishboliner–Krivelevich–Michaeli's conjecture. If

δ(G)≥n2,\delta(G)\geq \frac{n}{2},

then there exists a Hamilton cycle CC in GG such that

σmax⁡(C)≥δ(G).\sigma_{\max}(C)\geq \delta(G).

This conjecture is a directed analogue of discrepancy results for Hamilton cycles, predicting that a minimum-degree condition at least half the order forces a Hamilton cycle with sufficiently large oriented discrepancy. Its resolution is not indicated in the supplied text.

References

Primary source

Andrea Freschi and Allan Lo, “An oriented discrepancy version of Dirac's theorem”, arXiv:2211.06950 (2024).

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.