pith. sign in

arxiv: 2606.19851 · v1 · pith:FEEUVERDnew · submitted 2026-06-18 · 🧮 math.CO

An exact robust Ramsey theorem for matchings

Mengyuan Niu , Lanchao Wang This is my paper

Pith reviewed 2026-06-26 17:11 UTC · model grok-4.3

classification 🧮 math.CO
keywords Ramsey numbersmatchingss-connectorsmulticolour Ramseyrobust Ramsey theoremsexact thresholdsminimal counterexamples
0
0 comments X

The pith

The multicolour Ramsey number for matchings in any s-connector equals the sum of (t_j minus 1) over colours plus the maximum of 2s and s plus the largest t_j.

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

The paper determines the precise smallest N such that every N-vertex s-connector forces a monochromatic matching of size t_j in each of q colours. This removes the O(qs) additive error from earlier robust results and yields an exact closed-form expression. A reader would care because the formula matches the classical complete-graph case exactly once the robustness condition on the complement is imposed. The argument proceeds by assuming a minimal counterexample and applying a direct counting argument on monochromatic matchings inside s-connectors.

Core claim

For any vector t = (t_1, …, t_q) of positive integers, the Ramsey number R_s(t) is defined as the smallest N such that every s-connector G on N vertices satisfies G → (t_1 K_2, …, t_q K_2). The paper proves that this number equals exactly ∑(t_j − 1) + max{2s, s + max_j t_j}.

What carries the argument

Minimal-counterexample argument together with a new direct counting method for monochromatic matchings that works inside any s-connector.

If this is right

  • The dependence on the number of colours q disappears from the error term.
  • The exact threshold coincides with the known value for complete graphs once the s-connector condition is met.
  • The Gallai–Edmonds compression step used in prior work is replaced by a direct counting argument.
  • The result gives the precise boundary between graphs whose complements are K_{s,s}-free and those that are not.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same counting technique might yield exact thresholds for other forbidden subgraphs in the complement.
  • Small explicit checks for s=1 and small t vectors could verify the formula by hand.
  • If the counting method generalises, similar exact results may hold for robust versions of other Ramsey problems such as cycles or paths.

Load-bearing premise

Every s-connector admits a minimal counterexample to which the new monochromatic-matching counting method applies directly.

What would settle it

An s-connector on one fewer vertex than the stated formula whose edge colouring avoids all the required monochromatic matchings of sizes t_j.

read the original abstract

Keevash and Michaeli recently proved that, under the robustness assumption that \(G\) is an \(s\)-connector (i.e. \(\overline G\) is \(K_{s,s}\)-free), \(G\) has essentially the same multicolour Ramsey matching properties as complete graphs, with an additive error \(O(qs)\), where \(q\) is the number of colours. They asked whether the dependence on \(q\) can be removed. We answer this question in a stronger exact form. For \({\bf t}=(t_1,\ldots,t_q)\in\mathbb N_+^q\), let \(R_s({\bf t})\) be the smallest integer \(N\) such that every \(N\)-vertex \(s\)-connector \(G\) satisfies \( G\to (t_1K_2,\ldots,t_qK_2). \) We determine the exact value \[ R_s({\bf t})=\sum_{j\in[q]}(t_j-1)+ \max\left\{2s,\ s+\max_{j\in[q]}t_j\right\}. \] While Keevash and Michaeli's proof uses a compression algorithm based on the Gallai--Edmonds decomposition to reduce the colouring to a structured form, our proof is a direct minimal-counterexample argument together with a new counting method for monochromatic matchings which can be applied to \(s\)-connectors.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper determines the exact value of the robust multicolour Ramsey number R_s(t) for matchings, where an s-connector G (whose complement is K_{s,s}-free) satisfies G → (t_1 K_2, …, t_q K_2) precisely when the number of vertices reaches sum_{j}(t_j−1) + max{2s, s + max t_j}. The proof proceeds by minimal counterexample together with a new direct counting argument for monochromatic matchings that is asserted to apply to arbitrary s-connectors.

Significance. If correct, the result supplies an exact, parameter-free formula that removes the O(qs) additive error present in the earlier Keevash–Michaeli theorem and answers their question about q-independence. The new counting technique, which avoids the Gallai–Edmonds compression algorithm, is a methodological contribution that could extend to other robust Ramsey problems.

major comments (1)
  1. [minimal-counterexample argument and counting method] The central counting lemma (used inside the minimal-counterexample argument) is claimed to apply directly to every s-connector. It is not shown that the auxiliary graphs or subgraphs arising in the counting step remain s-connectors or satisfy the uniform degree conditions needed for the counting to go through when the extremal quantity is realized by 2s rather than s + max t_j. This verification is load-bearing for the exact formula.
minor comments (2)
  1. [Abstract and introduction] The vector t is written both as bold t and as (t_1,…,t_q); a single consistent notation would improve readability.
  2. [Introduction] The definition of an s-connector is repeated in several places; a single forward reference after the first occurrence would reduce redundancy.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a point in the proof that requires explicit verification. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: The central counting lemma (used inside the minimal-counterexample argument) is claimed to apply directly to every s-connector. It is not shown that the auxiliary graphs or subgraphs arising in the counting step remain s-connectors or satisfy the uniform degree conditions needed for the counting to go through when the extremal quantity is realized by 2s rather than s + max t_j. This verification is load-bearing for the exact formula.

    Authors: We agree that the manuscript does not explicitly verify that the auxiliary graphs arising during the counting step (obtained by deleting a small matching or considering induced subgraphs on the remaining vertices) remain s-connectors, nor does it separately check the degree conditions in the case where the extremal term is 2s. This verification is indeed necessary to confirm that the counting lemma applies uniformly. In the revised version we will insert a short auxiliary lemma (immediately preceding the counting argument) that confirms: (i) deletion of at most max t_j vertices or a matching of size less than s preserves the K_{s,s}-free property of the complement, and (ii) the minimum-degree lower bound inherited from the minimal-counterexample assumption continues to hold in both regimes of the max{2s, s + max t_j} expression. With this addition the counting step goes through without further changes to the overall argument. revision: yes

Circularity Check

0 steps flagged

No circularity: exact Ramsey number derived via independent minimal-counterexample counting on s-connectors

full rationale

The claimed exact formula for R_s(t) is obtained from a direct minimal-counterexample argument plus a new monochromatic matching counting method that applies to any s-connector (complement K_{s,s}-free). No step reduces the target quantity to a fitted parameter, self-definition, or load-bearing self-citation; the counting method is presented as newly developed for this setting and does not presuppose the formula. The derivation therefore remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of s-connectors and the applicability of a minimal-counterexample argument together with a new counting method to such graphs; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Standard definitions and properties of graphs, matchings, and the Ramsey arrow notation in combinatorial graph theory.
    These background facts are invoked to define s-connectors and the multicolour matching property.

pith-pipeline@v0.9.1-grok · 5783 in / 1134 out tokens · 32237 ms · 2026-06-26T17:11:28.647976+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Structural Reductions for Monochromatic Matchings and Ramsey Tilings

    math.CO 2026-06 conditional novelty 8.0

    A structural reduction framework for hypergraph colorings gives topology-free asymptotic AFL theorem and computable asymptotic densities for Ramsey tilings of graphs H in r-edge-colored K_n.

Reference graph

Works this paper leans on

29 extracted references · 15 canonical work pages · cited by 1 Pith paper

  1. [1]

    Applicable Analysis and Discrete Mathematics , volume=

    The Constructor-Blocker game , author=. Applicable Analysis and Discrete Mathematics , volume=

  2. [2]

    Journal of Graph Theory , volume=

    On the Constructor-Blocker game , author=. Journal of Graph Theory , volume=

  3. [3]

    and Shapira, A

    Gishboliner, L. and Shapira, A. , journal=. A generalized Tur

  4. [4]

    Gerbner, D. and Gy. Generalized. Journal of Combinatorial Theory, Series B , volume=. 2020 , publisher=

    2020

  5. [5]

    and Mogge, Y

    Boisson, C. and Mogge, Y. and Parreau, A. and Pierron, T. , journal=. Creating triangles in

  6. [6]

    , TITLE =

    Conlon, D. , TITLE =. Amer. Math. Monthly , FJOURNAL =. 2021 , NUMBER =. doi:10.1080/00029890.2021.1886845 , URL =

    work page doi:10.1080/00029890.2021.1886845 2021

  7. [7]

    Katona, G. O. H. and Nemetz, T. and Simonovits, M. , journal=. On a graph-problem of Tur

  8. [8]

    Journal of Combinatorial Theory, Series B , volume=

    Cycles of even length in graphs , author=. Journal of Combinatorial Theory, Series B , volume=

  9. [9]

    Studia Scientiarum Mathematicarum Hungarica , volume=

    On a problem of graph theory , author=. Studia Scientiarum Mathematicarum Hungarica , volume=

  10. [10]

    Canadian Journal of Mathematics , volume=

    Minimal regular graphs of girths eight and twelve , author=. Canadian Journal of Mathematics , volume=

  11. [11]

    , journal=

    Wenger, R. , journal=. Extremal graphs with no \(C^4\)'s, \(C^6\)'s, or \(C^

  12. [12]

    Random Structures & Algorithms , volume=

    Color-biased Hamilton cycles in random graphs , author=. Random Structures & Algorithms , volume=

  13. [13]

    arXiv preprint arXiv:2603.03139 , year=

    A very robust Ramsey theorem for matchings , author=. arXiv preprint arXiv:2603.03139 , year=

    arXiv

  14. [14]

    Matching Theory , author=

  15. [15]

    Cockayne, E. J. and Lorimer, P. J. , TITLE =. J. Aust. Math. Soc. , FJOURNAL =. 1975 , PAGES =. doi:10.2307/1997371 , URL =

    work page doi:10.2307/1997371 1975

  16. [16]

    , title =

    Gallai, T. , title =. A Magyar Tudom

  17. [17]

    and Hu, P

    Balogh, J. and Hu, P. and Simonovits, M. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2015 , PAGES =. doi:10.1016/j.jctb.2015.04.005 , URL =

    work page doi:10.1016/j.jctb.2015.04.005 2015

  18. [18]

    and Lenz, J

    Balogh, J. and Lenz, J. , TITLE =. Israel J. Math. , FJOURNAL =. 2013 , NUMBER =. doi:10.1007/s11856-012-0076-2 , URL =

    work page doi:10.1007/s11856-012-0076-2 2013

  19. [19]

    Simonovits, M. and S. Discrete Math. , FJOURNAL =. 2001 , NUMBER =. doi:10.1016/S0012-365X(00)00214-4 , URL =

    work page doi:10.1016/s0012-365x(00)00214-4 2001

  20. [20]

    Omidi, G. R. and Raeisi, G. , TITLE =. Discrete Math. , FJOURNAL =. 2024 , NUMBER =. doi:10.1016/j.disc.2023.113785 , URL =

    work page doi:10.1016/j.disc.2023.113785 2024

  21. [21]

    and Michaeli, P

    Keevash, P. and Michaeli, P. , TITLE =. arXiv e-prints , YEAR =. doi:10.48550/arXiv.2509.10679 , URL =. 2509.10679 , ARCHIVEPREFIX =

    work page doi:10.48550/arxiv.2509.10679

  22. [22]

    and Krivelevich, M

    Gishboliner, L. and Krivelevich, M. and Michaeli, P. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2022 , PAGES =. doi:10.1016/j.jctb.2022.01.003 , URL =

    work page doi:10.1016/j.jctb.2022.01.003 2022

  23. [23]

    and Krivelevich, M

    Gishboliner, L. and Krivelevich, M. and Michaeli, P. , TITLE =. J. Graph Theory , FJOURNAL =. 2023 , NUMBER =. doi:10.1002/jgt.22947 , URL =

    work page doi:10.1002/jgt.22947 2023

  24. [24]

    and Morris, P

    Han, J. and Morris, P. and Wang, G. and Yang, D. , TITLE =. Random Structures Algorithms , FJOURNAL =. 2024 , NUMBER =. doi:10.1002/rsa.21182 , URL =

    work page doi:10.1002/rsa.21182 2024

  25. [25]

    and Pehova, Y

    Nenadov, R. and Pehova, Y. , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2020 , NUMBER =. doi:10.1137/18M1211970 , URL =

    work page doi:10.1137/18m1211970 2020

  26. [26]

    , TITLE =

    Montgomery, R. , TITLE =. Adv. Math. , FJOURNAL =. 2019 , PAGES =. doi:10.1016/j.aim.2019.106793 , URL =

    work page doi:10.1016/j.aim.2019.106793 2019

  27. [27]

    and Hu, J

    Han, J. and Hu, J. and Ping, L. and Wang, G. and Wang, Y. and Yang, D. , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2024 , NUMBER =. doi:10.1017/S0963548323000378 , URL =

    work page doi:10.1017/s0963548323000378 2024

  28. [28]

    and Krivelevich, M

    Friedman, L. and Krivelevich, M. , TITLE =. Combinatorica , FJOURNAL =. 2021 , NUMBER =. doi:10.1007/s00493-020-4434-0 , URL =

    work page doi:10.1007/s00493-020-4434-0 2021

  29. [29]

    and Lew, A

    Krivelevich, M. and Lew, A. and Michaeli, P. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 2025 , PAGES =. doi:10.1016/j.jctb.2025.07.001 , URL =

    work page doi:10.1016/j.jctb.2025.07.001 2025