pith. sign in

arxiv: 2502.12596 · v4 · submitted 2025-02-18 · 🧮 math.CO

Asymptotic Bounds for t(3,n) and an Application to t(4,n)

Meng Ji , Yaping Mao , Ingo Schiermeyer This is my paper

Pith reviewed 2026-05-23 02:52 UTC · model grok-4.3

classification 🧮 math.CO
keywords mixed ramsey numbersirredundant setsramsey theoryasymptotic boundsedge coloringsindependent setsgraph theory
0
0 comments X

The pith

The mixed Ramsey number t(3,n) is at most order n to the 5/4 divided by log n.

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

The paper establishes that the mixed Ramsey number t(3,n) is O(n^{5/4}/log n). This quantity is the smallest N such that any red-blue coloring of the edges of the complete graph on N vertices contains either a 3-element irredundant set in blue or an n-element independent set in red. The new upper bound improves the previous best result and is strong enough to confirm a conjecture on the growth of t(4,n). The argument proceeds by combinatorial counting combined with probabilistic deletion to limit the size of irredundant sets that can avoid the desired structures.

Core claim

By combinatorial counting and probabilistic deletion, every red-blue coloring of the edges of K_N must contain either a 3-element irredundant set in the blue graph or an independent set of size n in the red graph once N exceeds a constant multiple of n^{5/4}/log n. Thus t(3,n) equals O(n^{5/4}/log n). The same technique verifies the conjecture of Chen, Hattingh and Rousseau that t(4,n) has order n^2/log^2 n.

What carries the argument

The mixed Ramsey number t(m,n), the smallest N forcing an m-element irredundant blue set or n-element red independent set in any 2-coloring of K_N.

If this is right

  • t(3,n) is bounded above by C n^{5/4}/log n for a fixed positive constant C.
  • The irredundant Ramsey number s(3,n) is pinned down up to a constant factor as well.
  • The 1993 conjecture on the asymptotic order of t(4,n) holds.
  • The same counting-plus-deletion technique controls the growth of these parameters for small fixed m.

Where Pith is reading between the lines

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

  • Matching lower bounds of the same order would fix the precise growth rate of t(3,n).
  • The method may adapt to obtain bounds for t(m,n) when m exceeds 4.
  • Because independent sets are special cases of irredundant sets, the new bound gives a quantitative comparison between mixed and classical Ramsey numbers.

Load-bearing premise

The combinatorial counting and probabilistic deletion steps correctly upper-bound the largest possible irredundant sets in every 2-edge-coloring.

What would settle it

A red-blue coloring of K_N for N larger than C n^{5/4}/log n with neither a 3-irredundant blue set nor an n-independent red set would falsify the upper bound.

read the original abstract

A set of vertices $X\subseteq V$ in a simple graph $G(V,E)$ is irredundant if each vertex $x\in X$ is either isolated in the induced subgraph $G[X]$ or else has a private neighbor $y\in V\setminus X$ that is adjacent to $x$ and to no other vertex of $X$. The \emph{mixed Ramsey number} $t(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ has an $m$-element irredundant set in the blue subgraph or an $n$-element independent set in the red subgraph. The irredundant Ramsey number $s(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ has an $m$-element irredundant set in the blue subgraph or an $n$-element irredundant set in the blue subgraph. In this paper, we determine $t(3,n)$ and $s(3,n)$ up to a constant factor by showing that $t(3,n)=O\left(n^{5/4}/{\log{n}}\right)$, which improved the best upper bound due to Rousseau and Speed in [Comb. Probab. Comput. 12 (2003), 653-660]. As an application, we verify a conjecture for $m=4$ proposed by Chen, Hattingh, and Rousseau in [J. Graph Theory 17(2) (1993), 193-206].

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

0 major / 3 minor

Summary. The paper proves that the mixed Ramsey number t(3,n) satisfies t(3,n) = O(n^{5/4}/log n), improving the 2003 upper bound of Rousseau and Speed. It likewise bounds the irredundant Ramsey number s(3,n) up to a constant factor and applies the t(3,n) result in §5 to confirm the m=4 case of a conjecture of Chen, Hattingh and Rousseau (1993). The central argument is a probabilistic deletion procedure (Theorem 3.1) that rests on a counting lemma (Lemma 3.2) and an explicit deletion step (§3.3).

Significance. If the stated bounds hold, the work supplies a concrete improvement to the best-known upper bound on t(3,n) together with a verification of an open conjecture on t(4,n). The explicit, standard combinatorial-probabilistic machinery (no hidden parameters or post-hoc restrictions) is a clear strength.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'determine t(3,n) and s(3,n) up to a constant factor' should indicate whether the matching lower bound is taken from the literature or proved in the paper.
  2. [§5] §5: a one-sentence restatement of the precise statement of the Chen-Hattingh-Rousseau conjecture would help readers who have not consulted the 1993 reference.
  3. [§3.3] Notation: the random-graph model used in the deletion argument could be named explicitly (e.g., G(n,p) with p = …) rather than described only procedurally.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the significance of the improved bound on t(3,n) and the verification of the Chen-Hattingh-Rousseau conjecture for m=4, and the recommendation of minor revision. The report accurately captures the main contributions and the probabilistic deletion method.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The claimed upper bound t(3,n)=O(n^{5/4}/log n) is obtained via an explicit probabilistic deletion argument (Theorem 3.1) that rests on a counting lemma (Lemma 3.2) and standard Ramsey-graph assumptions. These steps are derived from first-principles combinatorial counting and deletion, not from any fitted parameter, self-definition, or load-bearing self-citation. The improvement is over an external 2003 result by Rousseau and Speed, and the application to the m=4 case follows directly from the new bound without additional circular steps. The derivation chain is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard axioms of graph theory and set theory with no free parameters, ad-hoc axioms, or invented entities mentioned.

axioms (1)
  • standard math Basic definitions and properties of graphs, edge colorings, independent sets, and irredundant sets hold as standard in graph theory.
    Invoked implicitly throughout the definitions of t(m,n) and s(m,n).

pith-pipeline@v0.9.0 · 5821 in / 1392 out tokens · 30873 ms · 2026-05-23T02:52:12.778887+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Brewster, E.J

    R.C. Brewster, E.J. Cockayne, and C.M. Mynhardt, Irredundan t Ramsey numbers for graphs, J. Graph Theory 13(3) (1989), 283–290

    work page 1989

  2. [2]

    Brewster, E.J

    R.C. Brewster, E.J. Cockayne, and C.M. Mynhardt, The irredund ant Ramsey number, Quaest. Math. 13(2) (1990), 141–157

    work page 1990

  3. [3]

    Burger, J.H

    A.P. Burger, J.H. Hattingh, and J.H. van Vuuren, The mixed irredu ndant Ramsey numbers t(3, 7) = 18 and t(3, 8) = 22, Quaest. Math. 37(4) (2014), 571–589

    work page 2014

  4. [4]

    Burger and J

    A. Burger and J. Vuuren, The irredundance-related Ramsey nu mbers s(3, 8) = 21 and w(3, 8) = 21, Discrete Math. Theor. Comput. Soc. , ISS. ffhal-01666998 (2017)

    work page 2017

  5. [5]

    Chen, J.H

    G. Chen, J.H. Hattingh, and C.C. Rousseau, Asymptotic bounds f or irredundant and mixed Ramsey numbers, J. Graph Theory 17(2) (1993), 193–206

    work page 1993

  6. [6]

    Chen and C.C

    G. Chen and C.C. Rousseau, The irredundant Ramsey number s(3, 7), J. Graph Theory 19(2) (1995), 263–270

    work page 1995

  7. [7]

    Cockayne, G

    E.J. Cockayne, G. Exoo, J.H. Hattingh, and C.M. Mynhardt, The ir redundant Ramsey number s(4, 4), Util. Math. 41 (1992), 119–128

    work page 1992

  8. [8]

    Cockayne, J.H

    E.J. Cockayne, J.H. Hattingh, J. Kok, and C.M. Mynhardt, Mixed R amsey numbers and irredundant Tur´ an numbers for graphs,Ars Combin. 29 (1990), 57–68

    work page 1990

  9. [9]

    Cockayne, S.T

    E.J. Cockayne, S.T. Hedetniemi, D.J. Miller, Properties of heredita ry hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978), 461–468. 8

    work page 1978

  10. [10]

    Cockayne and C.M

    E.J. Cockayne and C.M. Mynhardt, The irredundant Ramsey num ber s(3, 3, 3) = 13, J. Graph Theory 18(6) (1994), 595–604

    work page 1994

  11. [11]

    E. J. Cockayne, G. MacGillivray, J. Simmons, CO-irredundant Ra msey Numbers for Graphs, J Graph Theory 34(2000), 258–268

    work page 2000

  12. [12]

    Erd¨ os and J.H

    P. Erd¨ os and J.H. Hattingh, Asymptotic bounds for irredunda nt Ramsey numbers, Quaest. Math. 16(3) (1993), 319–331

    work page 1993

  13. [13]

    Hattingh, On irredundant Ramsey numbers for graphs, J

    J.H. Hattingh, On irredundant Ramsey numbers for graphs, J. Graph Theory 14(4) (1990), 437–441

    work page 1990

  14. [14]

    Henningh and O.R

    M.A. Henningh and O.R. Oellermann, On upper domination Ramsey nu mbers of graphs, Discrete Math. 234 (2004), 125–135

    work page 2004

  15. [15]

    J. H. Kim, The Ramsey number R(3, t) has order of magnitude t2/ log t, Random Struct. Algor., 7 (1995), 173–207

    work page 1995

  16. [16]

    Krivelevich, A lower bound for irredundant Ramsey numbers, Discrete Math

    M. Krivelevich, A lower bound for irredundant Ramsey numbers, Discrete Math. 183 (1-3) (1998), 185–192

    work page 1998

  17. [17]

    Mynhardt, A

    C.M. Mynhardt, A. Roux, Irredundance. In: Haynes, T.W., Hedetniemi, S.T., Henning, M.A. (eds) Structures of Domination in Graphs. Developments in Mathem atics, vol 66. Springer, Cham

    work page

  18. [18]

    Rousseau and S

    C.C. Rousseau and S. E. Speed, Mixed Ramsey numbers revisited , Comb. Probab. Comput. 12 (2003), 653–660

    work page 2003

  19. [19]

    Shearer, A note on the independence number of triangle-f ree graphs, Discrete Math

    J.B. Shearer, A note on the independence number of triangle-f ree graphs, Discrete Math. 46 (1983), 83–87

    work page 1983

  20. [20]

    Spencer, Asymptotic bounds for Ramsey functions, Discrete Math

    J. Spencer, Asymptotic bounds for Ramsey functions, Discrete Math. 20 (1977), 69–76. 9

    work page 1977