Lower-bound conjecture for edge-ordered Ramsey numbers of degenerate graphs
Statement
An edge-ordered graph is a graph whose edges are equipped with a linear ordering. A graph is -degenerate if every induced subgraph has a vertex of degree at most . For an edge-ordered graph , let be its edge-ordered Ramsey number, and let denote the number of vertices of . Lower-bound conjecture. For every , there exists an infinite family of edge-ordered -degenerate graphs such that
The authors conjecture that such examples exist because they cannot rule out the stronger linear bound, and that this lower bound would make the polynomial upper bound tight up to the constant in the exponent. This conjecture remains open.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.