Near-linear saturation conjecture for edge-ordered graphs

From papers

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

sate(n,G)=O(n1+o(1)).sat_e(n,G)=O\left(n^{1+o(1)}\right).

The paper identifies this as the main general upper-bound problem and notes that the same bound would imply the corresponding bound for satmsat_m.

Progress summary

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

Sources & referencesView supporting material

Primary source

Vladimir Bošković and Balázs Keszegh, “Saturation of edge-ordered graphs”, arXiv:2408.00457 (2024).

Solutions 0

No solutions have been posted yet.