Polynomial bound conjecture for edge-ordered Ramsey numbers of degenerate graphs

An edge-ordered graph is a graph whose edges are equipped with a linear ordering. A graph is dd-degenerate if every induced subgraph has a vertex of degree at most dd. For an edge-ordered graph HH, let redge(H)r_{\operatorname{edge}}(H) be its edge-ordered Ramsey number. Polynomial bound conjecture. If HH is an edge-ordered dd-degenerate graph on nn vertices, then

redge(H)nO(d).r_{\operatorname{edge}}(H)\leq n^{O(d)}.

This would improve the paper's existing bound for edge-ordered Ramsey numbers of sparse graphs. The stronger linear analogue is also left unresolved, so this conjecture remains open.

Sources & referencesView supporting material

Primary source

Jacob Fox and Ray Li, “On edge-ordered Ramsey numbers”, arXiv:1906.08234 (2019).

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.