arxiv: 2604.08215 · v2 · submitted 2026-04-09 · 🧮 math.CO

Recognition: no theorem link

Ramsey numbers for regular induced subgraphs

Paul W. Dyson , Brendan D. McKay

Authors on Pith no claims yet

Pith reviewed 2026-05-12 01:56 UTC · model grok-4.3

classification 🧮 math.CO

keywords Ramsey numbersregular induced subgraphsgraph theoryinduced subgraphscombinatorial constructionsexact thresholdslower boundscomputer verification

0 comments

The pith

The smallest n forcing every graph on n vertices to contain a regular induced subgraph of order k is now known exactly for each k up to 5.

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

The paper examines the minimal vertex count n(k) that forces any graph on at least n(k) vertices to contain an induced regular subgraph on exactly k vertices. This threshold matters because it quantifies when balanced degree structures become unavoidable in arbitrary graphs, sharpening a classical Ramsey-style question in combinatorics. For k from 1 to 5 the authors pin down the exact thresholds by combining explicit constructions with exhaustive verification. They also raise the lower bounds on n(k) for k=6 and k=7 and strengthen the lower bound that holds for all larger k. The work therefore narrows the window in which the guaranteed appearance of such subgraphs must occur.

Core claim

We determine the exact value of the smallest n such that every graph on n vertices contains a regular induced subgraph of order k, for each k ≤ 5. For k = 6 and k = 7 we establish new lower bounds on this n, and we strengthen the general lower bound that applies for arbitrary k.

What carries the argument

The threshold function n(k) defined as the smallest integer guaranteeing a regular induced subgraph on exactly k vertices in every graph of that order, established through explicit avoiding constructions for lower bounds and exhaustive case analysis for exact values.

Load-bearing premise

The combinatorial constructions and exhaustive computer searches used to establish the exact values for small k and the improved lower bounds are complete and correct.

What would settle it

Discovery of a graph on the claimed n(k) vertices that lacks any regular induced subgraph of order k, or a graph on the new lower-bound size that already contains one, would refute the stated thresholds.

read the original abstract

A problem proposed by Erd\H{o}s, Fajtlowicz and Staton asks for the smallest $n$ for which every graph on $n$ vertices contains a regular induced subgraph of order at least $k$. A variation is to ask for a regular induced subgraph of order exactly $k$. In this paper we provide exact values for $k\le 5$ and lower bounds for $k=6$ and $k=7$. We also improve the general lower bound of Alon, Krivelevich and Sudakov [SIAM J. Disc. Math, 2008].

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.

Desk Editor's Note private letter to a colleague

Dyson and McKay pin down exact values for the smallest n forcing a regular induced subgraph on exactly k vertices when k is at most 5, plus a modest improvement to the 2008 general lower bound.

read the letter

This paper computes the exact Ramsey numbers for regular induced subgraphs of order exactly k, for k up to 5. It also gives lower bounds for k=6 and 7 and beats the general lower bound from Alon, Krivelevich and Sudakov in 2008 by a small amount. The exact small values are the part that was missing before. They come from explicit constructions that avoid the subgraphs (for the lower bounds) paired with arguments that every larger graph must contain one (for the upper bounds). For k=2,3,4,5 this is doable and the paper supplies the numbers. The general improvement is incremental but rests on a concrete construction that improves the earlier one. The work is careful and stays within standard methods of extremal graph theory. The soft spot is the upper bounds for k=4 and 5. These almost certainly use computer enumeration over graphs or degree sequences to show there is no counterexample on n-1 vertices. Any gap in the enumeration, isomorphism handling, or regularity check would change the exact value. The paper needs to make the search strategy, any code, and verification steps fully transparent so others can reproduce or spot-check them. Without that detail the exact claims are plausible but not yet ironclad. This is for specialists who track Ramsey numbers for induced subgraphs and want the small cases filled in. It is not going to reshape the broader theory, but the concrete numbers are useful to the people who care about this variant. It deserves a serious referee so the computational evidence can be examined by someone who knows the standard tools for these enumerations.

Referee Report

2 major / 2 minor

Summary. The paper studies the smallest n such that every graph on n vertices contains a regular induced subgraph on exactly k vertices. It claims to determine exact values of this number for all k ≤ 5, lower bounds for k = 6 and k = 7, and an improvement to the general lower bound of Alon, Krivelevich and Sudakov (2008).

Significance. If correct, the exact determinations for k ≤ 5 would settle the small cases of the Erdős–Fajtlowicz–Staton problem with concrete constructions and non-existence proofs, while the improved general bound would strengthen the known asymptotic results in induced-subgraph Ramsey theory. Explicit constructions and reliance on prior external bounds are positive features.

major comments (2)

[the section(s) stating the exact values for k = 4 and k = 5] The exact values claimed for k ≤ 5 rest on upper bounds that, for these small orders, are almost certainly obtained by exhaustive enumeration or computer-assisted case analysis over graphs on the candidate number of vertices. The manuscript must supply a complete description of the search procedure (generation of non-isomorphic graphs or degree sequences, regularity-checking algorithm, and termination criteria) together with any hand-verified base cases; without this documentation the exactness claim cannot be independently confirmed.
[the constructions and theorems giving the lower bounds] For the lower bounds (both the exact ones for k ≤ 5 and the new bounds for k = 6,7), the explicit constructions must be presented with sufficient detail to allow direct verification that the constructed graph on n−1 vertices indeed contains no regular induced subgraph on exactly k vertices.

minor comments (2)

A compact table summarizing the exact values and bounds for k = 1 through 7 would improve readability.
[Abstract] The abstract should state the numerical values obtained for k ≤ 5 rather than only announcing that exact values are provided.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments highlight important issues regarding reproducibility of our computational results and verifiability of constructions. We address each major comment below and will incorporate the requested details in a revised manuscript.

read point-by-point responses

Referee: [the section(s) stating the exact values for k = 4 and k = 5] The exact values claimed for k ≤ 5 rest on upper bounds that, for these small orders, are almost certainly obtained by exhaustive enumeration or computer-assisted case analysis over graphs on the candidate number of vertices. The manuscript must supply a complete description of the search procedure (generation of non-isomorphic graphs or degree sequences, regularity-checking algorithm, and termination criteria) together with any hand-verified base cases; without this documentation the exactness claim cannot be independently confirmed.

Authors: We agree that the exact values for k ≤ 5 rely on computer-assisted exhaustive search for the upper bounds, and that a full description of the procedure is required for independent verification. In the revised manuscript we will add a dedicated subsection that describes the search procedure in detail, including the method used to generate candidate graphs (non-isomorphic or by degree sequence), the algorithm for checking regularity of induced subgraphs on exactly k vertices, the termination criteria, and any base cases verified by hand. This addition will make the exact determinations fully reproducible. revision: yes
Referee: [the constructions and theorems giving the lower bounds] For the lower bounds (both the exact ones for k ≤ 5 and the new bounds for k = 6,7), the explicit constructions must be presented with sufficient detail to allow direct verification that the constructed graph on n−1 vertices indeed contains no regular induced subgraph on exactly k vertices.

Authors: We acknowledge that the constructions establishing the lower bounds (for both the exact values when k ≤ 5 and the new bounds for k = 6 and 7) must be presented with enough explicit information for direct verification. In the revision we will expand the relevant sections to include complete descriptions of each construction—such as adjacency lists, explicit parameters, or references to standard graphs—sufficient to confirm that the graph on n−1 vertices has no regular induced subgraph of order exactly k. This will address the verifiability concern without altering the stated bounds. revision: yes

Circularity Check

0 steps flagged

No circularity; results rest on explicit constructions and external citation.

full rationale

The paper claims exact Ramsey numbers for k≤5 via explicit graph constructions (lower bounds) and proofs or exhaustive case analysis (upper bounds), plus an improved general lower bound building on the external citation to Alon, Krivelevich and Sudakov. No self-definitional loops, fitted parameters renamed as predictions, load-bearing self-citations, or ansatzes smuggled via prior work appear in the abstract or claimed chain. The derivation is self-contained combinatorial reasoning independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard definitions of graphs, induced subgraphs, and regularity together with explicit constructions; no free parameters, new entities, or ad-hoc axioms are introduced beyond classical graph theory.

axioms (1)

standard math Standard definitions and basic properties of undirected simple graphs, induced subgraphs, and regular graphs of given degree.
Invoked throughout to define the objects whose existence is guaranteed.

pith-pipeline@v0.9.0 · 5386 in / 1194 out tokens · 51828 ms · 2026-05-12T01:56:24.478490+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Forward citations

Cited by 1 Pith paper

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

Pair-Trace Absorption Certificates for Regular Induced Subgraphs
math.CO 2026-04 unverdicted novelty 6.0

The paper gives exact quotient formulas and absorption certificates for deletion-tail obstructions in q-modular witnesses, using oriented differences in complement-orbit coordinates and linear algebra over F_2.

Reference graph

Works this paper leans on

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

[1]

N. Alon, M. Krivelevich and B. Sudakov, Large nearly regular induced subgraphs,SIAM J. Discrete Math.,22(2008) 1325–1337. doi:10.1137/070704927

work page doi:10.1137/070704927 2008
[2]

Balakrishnan and V

N. Balakrishnan and V. B. Nevzorov, A Primer on Statistical Distributions, Wiley- Interscience, 2003

work page 2003
[3]

Bollob´ as, Private communications, 1997

B. Bollob´ as, Private communications, 1997

work page 1997
[4]

P. W. Dyson and B. D. McKay, Regular induced subgraphs, internet resource athttps: //users.cecs.anu.edu.au/~bdm/data/ramsey.html

work page
[5]

Erd˝ os, On some of my favourite problems in various branches of combinatorics, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, 69–79, Ann

P. Erd˝ os, On some of my favourite problems in various branches of combinatorics, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, 69–79, Ann. Discrete Math. 51, 1992

work page 1992
[6]

Erd˝ os, Some of my favorite solved and unsolved problems in graph theory,Quaes- tiones Math,16(1993) 333–350

P. Erd˝ os, Some of my favorite solved and unsolved problems in graph theory,Quaes- tiones Math,16(1993) 333–350

work page 1993
[7]

Erd˝ os, Some of my favourite problems in number theory, combinatorics, and geome- try, Combinatorics Week (Portuguese) (S˜ ao Paulo, 1994),Resenhas2(1995) 165–186

P. Erd˝ os, Some of my favourite problems in number theory, combinatorics, and geome- try, Combinatorics Week (Portuguese) (S˜ ao Paulo, 1994),Resenhas2(1995) 165–186

work page 1994
[8]

Fajtlowicz, T

S. Fajtlowicz, T. McColgan, T. Read and W. Staton, Ramsey numbers for induced regular subgraphs,Ars Combin.,39(1995) 149–154

work page 1995
[9]

Krivelevich, B

M. Krivelevich, B. Sudakov and N. Wormald, Regular induced subgraphs of a random graph,Random Structures Algorithms,38(2011) 235–250. doi:10.1002/rsa.20324

work page doi:10.1002/rsa.20324 2011
[10]

Liebenau, N

A. Liebenau, N. Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph,J. Eur. Math. Soc.,26(2024) 1–40

work page 2024
[11]

McDiarmid, On the method of bounded differences

C. McDiarmid, On the method of bounded differences. In: Surveys in Combinatorics. Lond. Math. Soc. Lect. Notes Ser., 141, 148–188, Cambridge University Press (1989)

work page 1989
[12]

B. D. McKay, Isomorph-free exhaustive generation,J. Algorithms,26(1998) 306–324

work page 1998
[13]

B. D. McKay and A. Piperno, Practical Graph Isomorphism, II,J. Symbolic Computa- tion,60(2013) 94–112

work page 2013
[14]

B. D. McKay, N. C. Wormald, Asymptotic Enumeration by Degree Sequence of Graphs of High Degree,Europ. J. Combinatorics,11(1990) 565–580

work page 1990
[15]

B. D. McKay, N. C. Wormald, Asymptotic enumeration by degree sequence of graphs with degreeso( √n),Combinatorica,11(1991) 369–382. 12

work page 1991