Pith. sign in

REVIEW 2 major objections 4 minor 24 references

Ramsey multiplicity for ordered graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves an amplification inequality for weighted ordered Ramsey multiplicity, showing that in every edge-coloring of a large ordered complete graph the minimum weighted number of order-preserving target copies grows as a power of t

desk verdict A clean, honest first paper on ordered Ramsey multiplicity: the amplification inequality and star bounds hold up, and the main defect is a fixable presentation gap in the perfect-matching section. read the letter →

arxiv 2608.02299 v1 pith:QDVMIIWK submitted 2026-08-03 math.CO

Mengya He , Yaping Mao , Bing Wei , Qinghong Zhao This is my paper
classification math.CO MSC 05C1505C3005C3505C55
keywords orderedRamseynumbermultiplicityweightedamplificationinequalitystarsperfectmatchingsregularitylemmaorder-preservingcopies
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces a weighted version of ordered Ramsey multiplicity and proves a general amplification inequality: for fixed ordered graphs G1,...,Gk with at least one edge each, the minimum weighted number of correctly colored order-preserving copies in a k-edge-coloring of K_n is at least the same minimum at any smaller host t (t at least the ordered Ramsey number) times C(n,h*)/C(t,h*), where h* is the smallest target size. The inequality immediately yields that the normalized multiplicity M_λ(n)/C(n,h*) is nondecreasing and bounded, so the multiplicity is Θ(n^{h*}) and there is a positive limiting density π_λ. The authors apply this to two concrete classes: two-sided ordered stars, where a balanced two-interval coloring supplies an upper bound matching the lower bound up to constants, and the family of ordered perfect matchings containing the extreme edge {1,2m}, which is shown to have multiplicity Θ(n^{2m}). A regularity-based lifting theorem shows that correct copies in a reduced coloring over regular clusters force many correct copies in the original ordered coloring. The result matters because it turns ordered Ramsey multiplicity from a per-graph computation into a consequence of a single monotonicity inequality.

What carries the argument

The amplification inequality (Theorem 2.1) is the central mechanism: a double-counting argument over all t-element subsets of the n-vertex host, together with the fact that the ratio C(n,h_i)/C(t,h_i) is minimized by the smallest target h*, turns a lower bound at the threshold t into a lower bound at every larger host n. This single inequality produces the growth rate M_λ(n)=Θ(n^{h*}), the existence of the limiting density π_λ, and all subsequent applications. Supporting machinery: the balanced two-interval coloring B_h(n) = C(⌊n/2⌋,h) + C(⌈n/2⌉,h), which kills all cross-color star copies and minimizes the monochromatic count among two-interval colorings; the random-coloring expectation uppe

What would settle it

For m=2, B_2 is a single ordered matching with edges {1,4} and {2,3}; an exact enumeration of all red-blue colorings of K_n for n ≤ 8, checking whether M(n;B_2,B_2) ≥ M(t;B_2,B_2)·C(n,4)/C(t,4) for every t ≥ R_2, would directly test the family-level amplification. A single coloring with fewer copies than the inequality demands refutes Theorem 4.3; exhaustive verification for these small orders either confirms the extension or exposes the missing definition.

Watch

Extended reading notes

Core claim

At the heart of the paper is Theorem 2.1: for every n ≥ t ≥ R(G1,...,Gk) and every k-edge-coloring of K_n, the weighted count of visible targets satisfies inequality (2), and consequently M_λ(n;G1,...,Gk) ≥ M_λ(t;G1,...,Gk) · C(n,h*)/C(t,h*). The proof double-counts pairs (X,F) where X is a t-vertex subset and F is a correctly colored copy inside X; every t-subset carries weighted multiplicity at least M_λ(t), and each copy of a graph with h_i vertices is counted in exactly C(n-h_i, t-h_i) subsets, the smallest ratio belonging to the smallest target h*. This yields the Θ(n^{h*}) growth and the limiting density. The same inequality is then specialized to ordered stars S_{r,s}, where the balan

Load-bearing premise

The load-bearing step for the perfect-matching results is the unstated extension of the weighted multiplicity and the amplification inequality from individual ordered graphs to the family B_m of ordered perfect matchings containing the edge {1,2m}: Theorem 4.3 invokes 'G_1=G_2=B_m in Equation (4)' without ever defining multiplicity for a family of graphs, and if that extension failed, the lower bound M(n;B_m,B_m) ≥ M(t;B_m,B_m)·C(n,2m)/C(t,2m) and the Θ(n^{2m}) theorem would

Editorial extensions

If this is right

  • For any fixed ordered graphs G1,...,Gk with smallest size h*, the minimum weighted number of correctly colored order-preserving copies in every k-edge-coloring of K_n is Θ(n^{h*}), and the normalized sequence M_λ(n)/C(n,h*) converges to a positive density π_λ.
  • For two-sided ordered stars, the lower bound from amplification and the upper bound from the balanced two-interval coloring match up to a constant: π_λ(S_{r1,s1},S_{r2,s2}) lies between RM_λ/C(R,h*) and min λ_i 2^{1-h*}; in the diagonal equal-size case this upper bound is exactly half the uniform random-coloring bound.
  • From Theorem 2.1 equation (5), every coloring of a large ordered complete graph contains, for some color i among the smallest targets, at least about M_λ(t)/(|J_t| λ_i) · n^{h_i}/t^{h_i} correctly colored copies of G_i.
  • For the family B_m of ordered perfect matchings containing {1,2m}, every red-blue coloring contains Θ(n^{2m}) monochromatic copies, with the limiting density bounded between M(R_m;B_m,B_m)/C(R_m,2m) and (2m-2)!/(2^{2m-2}(m-1)!).
  • The regularity lifting theorem shows that any weighted lower bound at the ordered Ramsey number R transfers to all larger hosts: inequality (29) gives a lower bound on the original coloring's density in terms of reduced copies.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The family-level step used for B_m suggests a general principle: amplification holds for any hereditary family of ordered graphs of a fixed order h as long as multiplicity is defined over the whole family; if valid, the same Θ(n^h) and density conclusions would apply to the family of all ordered matchings of size m, not only those containing {1,2m}.
  • The balanced two-interval coloring is a natural candidate for being asymptotically extremal for two-sided stars; the next test is whether a regularity-based matching lower bound can close the gap between RM_λ/C(R,h*) and λ_i 2^{1-h*} in the unweighted case.
  • For perfect matchings, the paper leaves a gap between the lower and upper density bounds; computing M(n;B_m,B_m) exactly for small m (e.g., m=2,3) would test whether the limiting density equals the random-coloring value or is strictly smaller.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper introduces a weighted version of Ramsey multiplicity for ordered graphs, M_λ(n; G_1, ..., G_k), and proves an amplification inequality (Theorem 2.1) asserting M_λ(n; G_1, ..., G_k) ≥ M_λ(t; G_1, ..., G_k) · C(n, h*)/C(t, h*) for t ≥ R and n ≥ t, where h* is the minimum order of the target graphs. It follows that M_λ(n) = Θ(n^{h*}) and that the normalized sequence M_λ(n)/C(n, h*) has a positive finite limit π_λ. The paper then applies these tools to two-sided ordered stars, obtaining lower bounds from amplification and upper bounds from balanced interval colorings, and to the family B_m of ordered perfect matchings on [2m] containing the edge {1, 2m}, obtaining Θ(n^{2m}) growth and density bounds. A final section develops a regularity-based lifting theorem for ordered colorings, showing that correctly colored copies in a Szemerédi-style reduced graph lift to many ordered copies in the original coloring.

Significance. If the results hold, this is a meaningful step into ordered Ramsey multiplicity, a topic that has so far received little systematic attention. The amplification inequality is simple but useful: it gives the correct polynomial order of growth for every fixed tuple of ordered graphs and establishes the existence of a limiting density. The star bounds are clean and improve over the uniform random-coloring bound by a factor of two in the symmetric case. The perfect-matching results address a natural family and give the first bounds of their kind. The regularity lifting theorem is a flexible tool that may be useful beyond this paper. The manuscript is generally transparent: lower bounds come from exact double counting, upper bounds from explicit constructions and random colorings, and no fitting or circular reasoning is present. The detailed proofs are a strength, as are the explicit constants in the star and matching estimates.

major comments (2)
  1. [Section 4, Definition 4.1 and Theorem 4.3] The proof of the perfect-matching lower bound (20) cites Equation (4), but Equation (4) is Theorem 2.1, which is stated only for k-tuples of ordered graphs. B_m is a family of ordered matchings, not a single ordered graph, and no family analogue of M_λ or of Theorem 2.1 has been defined or proved. The lower bound (20), the monotonicity of M(n;B_m,B_m)/C(n,2m), and the lower bound on π(B_m) in (22) all depend on this step. The missing argument is straightforward — define N_i(χ;F) as the number of i-colored copies of any member of a finite family F and repeat the double counting, noting that every copy on h vertices lies in exactly C(n-h, t-h) t-subsets — but it must be stated and proved. As written, Theorem 4.3 is incomplete because it invokes a theorem that does not formally apply.
  2. [Section 4, Definition 4.1 / Theorem 4.3] The notation is inconsistent: Definition 4.1 defines M_2(n;B_m), but Theorem 4.3 states results for M(n;B_m,B_m). No formal definition of M(n;B_m,B_m) is given. If M(n;B_m,B_m) is meant to be the two-family analogue with red copies of B_m and blue copies of B_m, this should be stated explicitly, together with the corresponding family version of the multiplicity function. This is presentationally tied to the previous point, but it is also a barrier to checking the statement of Theorem 4.3.
minor comments (4)
  1. [Section 4] In Theorem 4.3, the phrase 'by taking λ=1 and G_1=G_2=B_m in Equation (4)' is a type error: B_m is a family, not an ordered graph. Once the family version of the amplification inequality is stated, the proof of (20) should refer to that lemma instead.
  2. [Section 5, Lemma 5.5] In the induction step, after applying Lemma 5.4, the text says 'and that the pair is 4η_h(d)/d-regular.' This reads more clearly as 'and the pair (V'_i, V'_j) is 4η_h(d)/d-regular.' The current phrasing is a minor clarity issue, not a mathematical error.
  3. [Section 5, Theorem 5.7] The regularity lifting theorem is presented as a standalone result and is not used elsewhere in the paper. A sentence explaining its intended role — for example, how (29) could be used to transfer upper bounds on regular copies to lower bounds on M_λ(n) — would help the reader judge its significance.
  4. [Section 4, Definition 4.1] The definition of R(B_m) as the least N such that every red–blue coloring of K_N contains a monochromatic copy of some member of B_m is fine, but it should be explicitly connected to the general family multiplicity notation. In particular, the paper should state that R(B_m) is finite (which follows from the finite ordered Ramsey theorem).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; Section 4's family extension of Theorem 2.1 is a formal presentation gap but not a circular reduction.

full rationale

The derivation chain is self-contained. Theorem 2.1 is a direct double-counting argument over t-subsets using the defining minimum M_λ(t;G_1,...,G_k), and Corollary 2.3 obtains monotonicity, boundedness, the limit π_λ, and Θ(n^{h*}) from inequality (4) plus an explicit constant coloring. The star bounds combine the same inequality, standard random-coloring expectations, and an explicit two-interval construction. The perfect-matching upper bound is an explicit random-coloring expectation, and the matching lower bound follows from the same double count once the family version is stated. The only notable issue is formal: Definition 1.1 and Theorem 2.1 are stated for ordered graphs, while Theorem 4.3 writes "by taking λ=1 and G1=G2=B_m in Equation (4)" even though B_m is a family of ordered matchings, not one graph. This is a presentation/rigor gap—the double-counting argument extends verbatim to finite families by counting copies of all members—not a circular reduction. There are no load-bearing self-citations, no fitted parameters renamed as predictions, and no conclusion used as its own premise.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper is self-contained in its main arguments; it relies on standard combinatorial facts, the Ramsey theorem, and the Szemerédi regularity lemma. No free parameters are fitted to data; the constants η_h and δ_h are defined recursively to make the embedding lemma go through and are not empirical.

assumptions (4)
  • standard math Szemerédi's regularity lemma (Theorem 5.2) is valid for multi-edge-colorings of complete graphs.
    Quoted from [24] and used in Section 5 to find regular clusters and in the lifting theorem (Theorem 5.7).
  • standard math The classical Ramsey theorem ensures the ordered Ramsey number R(G_1,...,G_k) is finite, so the amplification inequality has a threshold to start from.
    Invoked in the introduction and used in Theorem 2.1 (t≥R) and Corollary 2.3.
  • domain assumption Each h-element subset of an ordered host supports at most one order-preserving copy of a fixed h-vertex ordered graph.
    Stated in the introduction and used to justify counting copies by vertex sets throughout, including in Theorem 2.1 and Theorem 2.4.
  • standard math Hölder's inequality in the optimization of Theorem 2.4.
    Used to derive the closed-form bound (13) for equal edge counts.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ramsey multiplicity for ordered graphs." pith.science (2026). https://pith.science/paper/QDVMIIWK

@misc{pith2026260802299,
  author       = {Pith},
  title        = {Pith review of: Ramsey multiplicity for ordered graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QDVMIIWK}},
  note         = {Machine review of arXiv:2608.02299}
}
abstract

Let \(\cG_1,\ldots,\cG_k\) be fixed vertex-ordered graphs, each containing at least one edge. The ordered Ramsey number \(\oR(\cG_1,\ldots,\cG_k)\) is the least integer \(N\) such that every \(k\)-edge-coloring of the ordered complete graph \(\cK_N\) contains an order-preserving copy of \(\cG_i\) in color \(i\) for some \(i\in[k]\). For positive weights \(\blambda=(\lambda_1,\ldots,\lambda_k)\), let \(\oM_{\blambda}(n;\cG_1,\ldots,\cG_k)\) denote the minimum weighted number of correctly colored, order-preserving copies of the target graphs over all \(k\)-edge-colorings of \(\cK_n\). When \(\blambda=\bf{1}\), \(\oM_{\bf{1}}(n;\cG_1,\ldots,\cG_k)=\oM(n;\cG_1,\ldots,\cG_k)\) is called the ordered Ramsey multiplicity. In this paper, we first establish the amplification inequality \[ \oM_{\blambda}(n;\cG_1,\ldots,\cG_k) \ge \oM_{\blambda}(t;\cG_1,\ldots,\cG_k) \frac{\binom{n}{\hmin}}{\binom{t}{\hmin}}, \] where $h_i=v(\cG_i),\hmin=\min_{i\in[k]}h_i$, and $n\ge t\ge\oR(\cG_1,\ldots,\cG_k)$. Let $\cS_{r,s}$ be the ordered star whose center has $r-1$ leaves to its left and $s-1$ leaves to its right, and let $\bB_m$ be the family of all ordered perfect matchings on $[2m]$ containing the edge $\{1,2m\}$. We apply the amplification inequality to obtain the multiplicity lower bounds for ordered stars and ordered perfect matchings. We then obtain the upper bound $\oM_{\boldsymbol\lambda} (n;\cS_{r_1,s_1},\cS_{r_2,s_2}) \le \min\{\lambda_1 B_{h_1}(n),\lambda_2 B_{h_2}(n)\}$ by constructions, where $B_{h_i}(n):= \binom{\lfloor n/2\rfloor}{h_i} + \binom{\lceil n/2\rceil}{h_i}$ and $h_i=r_i+s_i-1$ for $i\in [2]$. We also derive a random-coloring upper bound for ordered stars and prove \[\oM(n; \bB_m,\bB_m) \le \binom{n}{2m} \frac{(2m-2)!}{2^{2m-2}(m-1)!}.\] Finally, we establish a regularity-based lifting theorem for ordered colorings.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 3 linked inside Pith

  1. [1]

    Alon and A

    N. Alon and A. Shapira, Testing subgraphs in directed graphs,J. Comput. System Sci.69 (2004), 354–382

    2004

  2. [2]

    Axenovich and R

    M. Axenovich and R. R. Martin, A version of Szemerédi’s regularity lemma for multicolored graphs and directed graphs, arXiv:1106.2871

    arXiv

  3. [3]

    Balko, J

    M. Balko, J. Cibulka, K. Král, and J. Kynčl, Ramsey numbers of ordered graphs,Electron. J. Combin.27 (2020), P1.16. 19

    2020

  4. [4]

    Balko, V

    M. Balko, V. Jelínek, and P. Valtr, On ordered Ramsey numbers of bounded-degree graphs,J. Combin. Theory Ser. B134 (2019), 179–202

    2019

  5. [5]

    Balko and M

    M. Balko and M. Poljak, On off-diagonal ordered Ramsey numbers of nested matchings, Discrete Math.346 (2023), 113223

    2023

  6. [6]

    S. A. Burr and V. Rosta, On the Ramsey multiplicities of graphs—problems and recent results, J. Graph Theory4 (1980), 347–361

    1980

  7. [7]

    S. A. Choudum and B. Ponnusamy, Ordered Ramsey numbers,Discrete Math.247 (2002), 79–92

    2002

  8. [8]

    Conlon, J

    D. Conlon, J. Fox, C. Lee, and B. Sudakov, Ordered Ramsey numbers,J. Combin. Theory Ser. B122 (2017), 353–383

    2017

Show all 24 references
  1. [9]

    Conlon, J

    D. Conlon, J. Fox, B. Sudakov, and F. Wei, Threshold Ramsey multiplicity for odd cycles, Rev. Un. Mat. Argentina64 (2022), 49–68

    2022

  2. [10]

    Conlon, J

    D. Conlon, J. Fox, B. Sudakov, and F. Wei, Threshold Ramsey multiplicity for paths and even cycles,European J. Combin.107 (2023), 103612

    2023

  3. [11]

    Cox and D

    C. Cox and D. Stolee, Ordered Ramsey numbers of loose paths and matchings,Discrete Math. 339 (2016), 499–505

    2016

  4. [12]

    Franek and V

    F. Franek and V. Rödl, Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs,Graphs Combin.8 (1992), 299–308

    1992

  5. [13]

    A. W. Goodman, On sets of acquaintances and strangers at any party,Amer. Math. Monthly 66 (1959), 778–783

    1959

  6. [14]

    R. L. Graham, B. L. Rothschild, and J. H. Spencer,Ramsey Theory, 2nd ed., Wiley, New York, 1990

    1990

  7. [15]

    Harary and G

    F. Harary and G. Prins, Generalized Ramsey theory for graphs IV: The Ramsey multiplicity of a graph,Networks4 (1974), 163–173

    1974

  8. [16]

    Hyde, J.-B

    J. Hyde, J.-B. Lee, and J. A. Noel, Turán colourings in off-diagonal Ramsey multiplicity, Electron. J. Combin.32 (2025), P2.14

    2025

  9. [17]

    Huang, J

    T. Huang, J. Yang and Y. Chen, On the threshold Ramsey multiplicity conjectures for paths and even cycles. arXiv preprint arXiv:2606.01996[math.CO]

    arXiv

  10. [18]

    M. S. Jacobson, On the Ramsey multiplicity for stars,Discrete Math.42 (1982), 63–66

    1982

  11. [19]

    K. G. Milans, D. Stolee, and D. B. West, Ordered Ramsey theory and track representations of graphs,J. Combin.6 (2015), 445–456. 20

    2015

  12. [20]

    Moss and J

    E. Moss and J. A. Noel, Off-diagonal Ramsey multiplicity, arXiv:2306.17388

    arXiv

  13. [21]

    Neidinger and D

    D. Neidinger and D. B. West, Ramsey numbers of interval 2-chromatic ordered graphs,Graphs Combin.35 (2019), 1065–1076

    2019

  14. [22]

    Parczyk, S

    O. Parczyk, S. Pokutta, C. Spiegel, and T. Szabó, New Ramsey multiplicity bounds and search heuristics,Found. Comput. Math.25 (2025), 1777–1814

    2025

  15. [23]

    F. P. Ramsey, On a problem of formal logic,Proc. London Math. Soc.30 (1930), 264–286

    1930

  16. [24]

    Szemerédi,Regular partitions of graphs, in: Problèmes combinatoires et théorie des graphes (Colloq

    E. Szemerédi,Regular partitions of graphs, in: Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, Vol. 260, CNRS, Paris, 1978, pp. 399–401. 21

    1976

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.