Almost-linear saturation conjecture for edge-ordered graphs

Let GG be an edge-ordered graph, and let sate(n,G)sat_e(n,G) denote its edge-ordered saturation function. Almost-linear saturation conjecture. For every edge-ordered graph GG,

sate(n,G)=O(nlogn).sat_e(n,G)=O(n\log n).

This is stated as a stronger conjecture than the paper's general O(n1+o(1))O\left(n^{1+o(1)}\right) upper-bound conjecture. The authors regard it as plausible by analogy with the known upper bound for semisaturation.

Sources & referencesView supporting material

Primary source

Vladimir Bošković and Balázs Keszegh, “Saturation of edge-ordered graphs”, arXiv:2408.00457 (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.