{"id":"b6c7572d-7a63-44a7-98d7-73795dd69275","arxiv_id":"2502.02155","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":0.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of ordered Ramsey numbers for graphs and hypergraphs, summarizing recent bounds and listing open problems.","lead":"For any two-coloring of a large ordered complete graph, you are guaranteed to find a copy of a given ordered pattern; ordered Ramsey numbers quantify how large is large. This survey collects the recent bounds, open problems, and connections to geometry for these numbers.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 14 appears to misstate the Mubayi–Suk relation: for q=2 the printed index k−q+1 gives MP_{k−1}^{(k)}, not the MP_{k+1}^{(k)} claimed in the surrounding text; the correct index is likely k+q−1.","rationale":"The reader's conditional verdict focused on the survey's reliance on unpublished references, especially [6]. That is a legitimate concern about verifiability. However, the sharper load-bearing issue is internal: Theorem 14, one of the survey's central stated connections between ordered and unordered hypergraph Ramsey numbers, is inconsistent with the sentence introducing it and is plainly false under the q=2, k=3 instantiation as printed. Since the paper's advertised contribution is accurate summarization, a displayed theorem that cannot be used as stated is a real accuracy defect. The defect appears to be a typographical sign error rather than a conceptual failure: the correct index should almost certainly be k+q−1, giving a monotone path with q edges. This is easily fixed, so the appropriate verdict remains CONDITIONAL rather than REJECT. I partially agree with the reader's weakest assumption: both concern the correctness of reported results, but the specific load-bearing weakness identified here is an internal misstatement of a published theorem, not an unpublished citation.","tokens_in":21184,"tokens_out":16739,"duration_ms":165559,"concrete_test":"Check the statement of the corresponding theorem in Mubayi and Suk [64] (published version in J. Combin. Theory Ser. B, 2017). If the middle term is R_<(K_n^{(k)}, MP_{k+q−1}^{(k)}) rather than MP_{k−q+1}^{(k)}, then Theorem 14 in the survey has a sign error and must be corrected. As an independent sanity check, instantiate q=2 and k=3: the printed middle term becomes R_<(K_n^{(3)}, MP_2^{(3)}), which is trivially 2, while the claimed inequality would force R(K_3;2)≤2 for n=6, a false statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 presents Theorem 14 as the 'surprising relation' connecting off-diagonal ordered Ramsey numbers of monotone k-uniform paths to classical hypergraph Ramsey numbers. As printed: R(K^{(k−1)}_{⌊n/q⌋};q) ≤ R_<(K^{(k)}_n, MP^{(k)}_{k−q+1}) ≤ R(K^{(k−1)}_n;q). But the paragraph immediately before says that for q=2 this concerns R_<(K^{(k)}_n, MP^{(k)}_{k+1}). For q=2, k−q+1 = k−1, and MP^{(k)}_{k−1} is not MP^{(k)}_{k+1}; for k=3, MP^{(3)}_2 is a 2-vertex hypergraph with no edges, so the middle term is trivial (it does not force anything beyond N≥2) and the stated lower bound R(K^{(2)}_{⌊n/2⌋};2)≤2 would be false for n≥6. The internally consistent reading is that the index should be k+q−1, giving a monotone path with q edges. This is a concrete accuracy defect in one of the paper's central advertised connections, and it is independent of the unpublished-reference caveat. The fix is a one-character correction if confirmed against [64], but as written the theorem cannot be used by a reader.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This survey synthesizes the recent literature on ordered Ramsey numbers. Section 2 covers ordered graphs: general bounds via degeneracy and interval chromatic number (Theorems 1-3), bounded-bandwidth paths (Theorem 5), off-diagonal matchings versus triangles, minimum ordered Ramsey numbers (Theorem 6), exact formulas for alternating paths and monotone cycles (Proposition 8, Theorem 9), and multicolor extensions. Section 3 covers ordered hypergraphs: monotone paths and the Erdos-Szekeres connection (Theorems 11-13), a relation between ordered Ramsey numbers and classical hypergraph Ramsey numbers (Theorem 14), and bounds for sparse 3-uniform hypergraphs (Theorems 16-17). Section 4 covers edge-ordered Ramsey numbers (Theorems 19-21). The paper compiles 16 open problems and 5 conjectures with attributions, and it explicitly disclaims exhaustiveness. No proofs are given; all statements are attributed to the literature.","tokens_in":21444,"tokens_out":58158,"duration_ms":485599,"significance":"If the reported results are accurate, this is a useful and timely reference: it appears to be the only recent survey devoted specifically to ordered Ramsey numbers, it covers the graph, hypergraph, and edge-ordered settings in one place, and it gives an attributed catalogue of open problems (Problems 1-16, Conjectures 1-5) that researchers can use directly. The author is a principal contributor to the area, and the bibliography is current through 2024. The connections drawn (Erdos-Szekeres theorem, geometric Ramsey numbers, k-queue graphs, Dedekind numbers) are presented clearly. Because the survey contains no derivations, its value rests entirely on the reliability of its attributions and displayed formulas; at present that reliability is compromised by at least one load-bearing misstatement (Theorem 14) and by the use of two non-public references ([3], [6]), so the manuscript needs revision before it can serve as the citation of record.","major_comments":[{"comment":"Theorem 14 is internally inconsistent and, as printed, false. The displayed statement is R(K^{(k-1)}_{floor(n/q)}; q) <= R_<(K^{(k)}_n, MP^{(k)}_{k-q+1}) <= R(K^{(k-1)}_n; q), while the immediately preceding paragraph says that the case q=2 concerns R_<(K^{(k)}_n, MP^{(k)}_{k+1}). For q=2 the printed index gives k-q+1 = k-1, so the middle term involves MP^{(k)}_{k-1}, a monotone path on k-1 vertices with no edges; the middle quantity is then trivially at most k-1 (for N = k-1 any coloring contains a blue copy), and the lower bound would assert R(K^{(k-1)}_{floor(n/2)}; 2) <= k-1, which is false (e.g., k=3 and n>=6 gives R(K^{(2)}_3; 2) = R(3,3) = 6 <= 2). The reading consistent with the surrounding text and with Conjecture 4 is MP^{(k)}_{k+q-1} (a monotone path with q edges), and the statement must quantify q >= 2 as well. Please correct the index (verifying the exact statement against [64]) and the quantifiers; as written, this advertised 'surprising relation' between ordered and classical hypergraph Ramsey numbers cannot be used by a reader.","section":"3.2, Theorem 14"}],"minor_comments":[{"comment":"Typographical and name errors: 'Colon, Fox, Lee, and Sudakov' (Section 2.1, before Problem 3) should be 'Conlon, Fox, Lee, and Sudakov'; 'mathchings' (Section 2.6) should be 'matchings'; 'dentote' (Section 3, first paragraph) should be 'denote'; reference [3] gives 'revisitied' for 'revisited'; reference [46] lists 'Neeidinger' for 'Neidinger'.","section":"2.1; 2.6; 3; refs"},{"comment":"In the paragraph after Theorem 5, the constant 'c = c(t)' should be 'c = c(k)', and the sentence describing the bound as valid 'for all s, t and n' uses an undefined parameter t (presumably k). The notation K_<^n in R_<(P_{k,n}, K_<^n) should be rendered as K^<_n, the ordered complete graph on n vertices.","section":"2.2"},{"comment":"The lower bound 'R_<(M_<, K_3) >= O((n/log n)^{4/3})' for ordered matchings should use Omega, not O, as the notation '>= O(...)' is meaningless as printed.","section":"2.3"},{"comment":"In Conjecture 4, R_<(K^{(k)}, MP^{(k)}_{k+1}) is missing the subscript n on the clique and should read R_<(K^{(k)}_n, MP^{(k)}_{k+1}). Also, the opening sentence of Section 3.2 refers to 'the classical Ramsey numbers R(K^{(k-1)}_n)', whereas Theorem 14 involves q-color Ramsey numbers; the wording should be aligned.","section":"3.2"},{"comment":"Several stated results and open problems rest on non-public references: [6] ('In preparation, 2024') supports the theorem R_<(M_<; q) = n^{Theta(q)} for matchings with interval chromatic number 2 and Problems 10-13, while [3] ('Submitted, 2024') is cited in Section 3.1. Since a survey is meant to be a stable reference, please replace these with publicly available preprints or published versions, or explicitly label the statements as conditional on forthcoming work.","section":"2.6 and 3.1"}],"recommendation":"major_revision","confidential_remarks":"The survey is balanced: the author's own substantial contributions are cited alongside the independent work of Conlon-Fox-Lee-Sudakov, Mubayi-Suk, Moshkovitz-Shapira, Fox-Li, and Girao-Janzer-Janzer, and I saw no evidence of biased attribution. Two points may warrant the editor's attention: (i) the main new results and problems in Section 2.6 are tied to the author's own 'In preparation' paper [6], so the editor may wish to require a public version before or at acceptance; (ii) Theorem 14 concerns a frequently cited result (Mubayi-Suk, JCTB 2017), and since this survey is likely to become the citation of record, the author should verify the corrected index k+q-1 directly against the source. The manuscript fits the scope of a combinatorics journal well."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one for the field, not for the result: it's a survey, and its value is in the organized summary of where ordered Ramsey numbers stand, plus a catalogue of open problems. The good news is that it covers the right ground—graph ordered Ramsey numbers, hypergraph monotone paths, edge-ordered variants—and connects them to the Erdős–Szekeres theorem and geometric Ramsey numbers. The bad news is that it has at least one load-bearing typo and leans on a couple of unpublished references.\n\nWhat it does well: it gives a readable, structured entry point to a young and active area. The notation is mostly clear, and the open problems are genuinely useful; several are attributed to the right people. The section on monotone paths and the Erdős–Szekeres theorem is a nice way to motivate the whole subject.\n\nWhere the soft spots are: Theorem 14, as printed, is not usable. The index in MP^{(k)}_{k−q+1} gives MP^{(k)}_{k−1} for q=2, which is an empty hypergraph, while the text just before says the result concerns MP^{(k)}_{k+1}. The internally consistent reading is that the index should be k+q−1. This is a one-character fix, but it should be caught in proofreading, and it is in one of the paper's advertised connections to classical hypergraph Ramsey numbers. Separately, references [6] and [3] are 'in preparation' and 'submitted' with no public versions; some stated bounds and open problems rest on those. For a survey, that is a real caveat. There are also typos like 'Colon' for 'Conlon' and 'mathchings' for 'matchings'.\n\nThe survey itself is honest about being non-exhaustive, and the summary of results matches the original papers I know well enough to check. The unpublished entries are flagged as such, which is something. But the Theorem 14 misstatement needs to be fixed before I would trust the survey as a reference.\n\nWho this is for: researchers who want a map of the area, especially graduate students and people entering ordered Ramsey theory. It is not a contribution to the literature in the sense of new theorems; its contribution is organizational. I would send it to a referee because it deserves a careful read and the typos and unpublished references would be caught, but I would not accept it as-is. If the author fixes the theorem statement and marks the in-preparation work, it becomes a serviceable survey.\n\nRecommendation: engage with it, but require those fixes before publication. The field is real, and the survey fills a gap.","headline":"A readable survey with real organizing value, but one load-bearing typo in Theorem 14 and two unpublished references keep it from being a reliable reference as-is.","tokens_in":21957,"tokens_out":4891,"would_cite":true,"duration_ms":40069,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D10","05C55","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper surveys ordered Ramsey numbers and reports that imposing a linear order on vertices can inflate Ramsey numbers far beyond the unordered case, while identifying structural parameters that restore polynomial bounds.","keywords":["ordered Ramsey numbers","Ramsey theory","ordered graphs","interval chromatic number","bandwidth","monotone paths","edge-ordered Ramsey numbers","Erdős–Szekeres theorem"],"falsifier":"A concrete check: once the in-preparation and submitted references appear, verify whether their stated bounds still hold; if either fails, the corresponding survey sections on multicolor ordered matchings and the Erdős–Szekeres reformulation would be wrong. Alternatively, a single ordered graph of bandwidth 2 with ordered Ramsey number exceeding C $n^{{4+ε}}$ would disprove the strongest theorem the survey reports.","tokens_in":20943,"feed_emoji":"📐","tokens_out":7982,"duration_ms":68394,"temperature":0.7,"pith_summary":"Ordered Ramsey numbers ask how large a complete graph with linearly ordered vertices must be before every red-blue edge coloring contains a monochromatic copy of a given ordered graph in the prescribed order. The survey's thesis is that imposing this order changes the quantitative story: sparse ordered graphs such as matchings can have superpolynomial ordered Ramsey numbers, whereas unordered bounded-degree graphs have linear Ramsey numbers. It gathers the main upper and lower bounds, highlights parameters such as interval chromatic number and bandwidth that restore polynomial growth, records exact formulas tied to the Erdős–Szekeres theorem, and lists open problems spanning multicolor, hypergraph, and edge-ordered variants.","feed_headline":"Vertex order can make sparse graphs Ramsey-hard","feed_subtitle":"A survey collects bounds, exact formulas, and open problems where ordering vertices changes the story.","key_machinery":"The load-bearing objects are the ordered Ramsey number R_<(G_<,H_<), defined as the smallest N such that every two-coloring of the ordered complete graph K_N^< yields a red copy of G_< or a blue copy of H_<, and the structural parameters used to bound it: interval chromatic number (the fewest intervals into which the vertex set can be partitioned so no edge lies inside an interval), degeneracy, and bandwidth (longest edge length). The named example carrying the connection to classical geometry is the monotone path MP_n^<, whose exact ordered Ramsey number (n-1)^2+1 is equivalent to the Erdős–Szekeres lemma on monotone subsequences.","core_discovery":"The author's aim is to establish that ordered Ramsey numbers form a subject with its own quantitative laws, distinct from classical Ramsey numbers. The survey reports that sparse ordered graphs can be extremely Ramsey-hard—there exist ordered matchings on n vertices with R_<(M_<) ≥ $n^{{C log n / log log n}}$—while bounded interval chromatic number and bounded degeneracy restore polynomial growth, R_<(G_<) ≤ $n^{{32 d log χ}}$. For monotone paths and cycles the survey records essentially sharp or exact results, including R_<(MC_r^<, MC_s^<) = 2rs - 3r - 3s + 6 and the monotone path formula that underlies the Erdős–Szekeres lemma. It presents the current best bound R_<(P_{k,n}^<) ≤ C $n^{{4+ε}}$ for bounded-bandwidth graphs and a list of open problems that mark where the subject's limits sit.","pith_inferences":["One step beyond the paper: interval chromatic number may be the operative parameter for algorithmic ordered Ramsey computations, since degree alone is insufficient; a testable extension would be to compute ordered Ramsey numbers of random ordered graphs with interval chromatic number 2 and growing degree.","The near-quartic upper bound versus quadratic lower bound for powers of monotone paths suggests the true growth is closer to quadratic, as the cited authors conjecture; if so, all bounded-bandwidth ordered Ramsey numbers would be near-quadratic in n.","The connection between monotone hyperpaths and antichains suggests a new route to the Erdős–Szekeres conjecture: improving upper bounds on R_<(MP_n^{(3)}) is equivalent to an enumerative problem on antichains, which could be attacked computationally.","The edge-ordered section points toward a wider principle: when the order is on edges rather than vertices, finiteness is non-trivial and requires completely different arguments; extending the exponential-type bounds to edge-ordered hypergraphs would be a natural next test."],"forward_implications":["If the reported bounds are correct, every ordered graph with fixed interval chromatic number and fixed degeneracy has a polynomial ordered Ramsey number, so Ramsey-type arguments for such ordered graphs do not need to pass through exponential bounds.","The exact monotone-cycle formula transfers directly to convex and geometric Ramsey numbers, giving R_c(C_n) = R_g(C_n) = 2n^2 - 6n + 6 for cycles.","The superpolynomial lower bound for ordered matchings means that ordered Ramsey theory is genuinely different from unordered Ramsey theory even for sparse graphs.","A positive answer to the survey's open problem about powers of monotone paths would replace the n^{4+o(1)} bound by a near-quadratic one, sharpening the whole bounded-bandwidth picture.","The survey's open problems, especially the off-diagonal matching-versus-triangle problem, identify where known techniques stop and mark concrete targets for new constructions."],"supporting_citations":[{"why":"One of the two foundational systematic studies; supplies the superpolynomial matching lower bound, the bandwidth bound, and the exact monotone cycle formula.","marker":"[13]"},{"why":"The other foundational systematic study; proves superpolynomial lower bounds for ordered matchings and polynomial bounds via interval chromatic number and degeneracy.","marker":"[27]"},{"why":"Yields the strongest currently known bound R_<(P_{k,n}^<) ≤ C n^{4+ε} for powers of monotone paths.","marker":"[48]"},{"why":"Provides exact ordered Ramsey numbers for monotone k-uniform paths, including the formula underlying the Erdős–Szekeres theorem.","marker":"[62]"},{"why":"Improves lower bounds for random ordered matchings and proves superlinear minimum ordered Ramsey numbers for random regular graphs.","marker":"[12]"},{"why":"Bounds off-diagonal ordered Ramsey numbers of nested matchings versus triangles; its lower bounds improve known k-queue graph chromatic bounds.","marker":"[7]"},{"why":"Gives exponential-type upper bounds on edge-ordered Ramsey numbers and polynomial bounds for bounded degeneracy.","marker":"[44]"},{"why":"Establishes the off-diagonal matching-versus-triangle results and the conjecture on almost all interval-chromatic-2 matchings.","marker":"[72]"}],"fun_headline_variants":["Sparse graphs turn Ramsey-hard when ordered","Why ordered Ramsey numbers defy classical intuition","Survey maps the wild world of ordered Ramsey numbers","Ordered Ramsey: new bounds, exact formulas, open problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The survey's picture is only as reliable as the cited results, and several of them have not yet been published, so a reader cannot yet independently verify those pieces.","fun_headline_variants_meta":{"raw":{"variants":["Sparse graphs turn Ramsey-hard when ordered","Why ordered Ramsey numbers defy classical intuition","Survey maps the wild world of ordered Ramsey numbers","Ordered Ramsey: new bounds, exact formulas, open problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000283,"raw_usage":{"total_tokens":1617,"prompt_tokens":837,"completion_tokens":780,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":453,"completion_tokens_details":{"reasoning_tokens":721}},"tokens_in":453,"tokens_out":780,"duration_ms":7735,"temperature":1.0,"reasoning_tokens":721,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T13:06:44.466809+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: once the in-preparation and submitted references appear, verify whether their stated bounds still hold; if either fails, the corresponding survey sections on multicolor ordered matchings and the Erdős–Szekeres reformulation would be wrong. Alternatively, a single ordered graph of bandwidth 2 with ordered Ramsey number exceeding C $n^{{4+ε}}$ would disprove the strongest theorem the survey reports.","supporting_citations":[{"cited_title":"Moshkovitz and A","cited_arxiv_id":null,"evidence_quote":"Provides exact ordered Ramsey numbers for monotone k-uniform paths, including the formula underlying the Erdős–Szekeres theorem."},{"cited_title":"Balko and M","cited_arxiv_id":null,"evidence_quote":"Bounds off-diagonal ordered Ramsey numbers of nested matchings versus triangles; its lower bounds improve known k-queue graph chromatic bounds."},{"cited_title":"Fox and R","cited_arxiv_id":null,"evidence_quote":"Gives exponential-type upper bounds on edge-ordered Ramsey numbers and polynomial bounds for bounded degeneracy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the off-diagonal matching-versus-triangle results and the conjecture on almost all interval-chromatic-2 matchings."}],"review_version":1}