REVIEW 2 minor 8 references
Induced/Incomparable versus Ramsey
T0 review · 0 major / 2 minor · reviewed 2026-06-30 · grok-4.3
Pith's one-line read For any tree on k vertices, the largest graph where every induced k-subgraph is the tree or incomparable to it has size at most (k-1)^2.
desk verdict This paper defines H-exact graphs and gives matching constructions plus upper bounds for f(H) on trees, stars, paths, and matchings. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The H-exact condition, requiring every induced k-vertex subgraph to be isomorphic to H or incomparable to H.
What would settle it
A single graph on more than (k-1)^2 vertices in which every induced subgraph on k vertices is either a fixed tree T or incomparable to T would falsify the upper bound.
Extended reading notes
Core claim
The central claim is that f(T) for a tree T on k >= 3 vertices satisfies (k-1)(ceil(k/2)-1) <= f(T) <= (k-1)^2, with the exact determinations f(K_{1,k-1}) = (k-1)(k-2) for k >= 4, f(P_k) = (k-1)^2/2 when k odd and (k-1)(k-2)/2 +1 when even for k >= 5, and f(nK_2) = 3n for n=2,3 and 4n-4 for n >=4.
Load-bearing premise
Explicit constructions of graphs G exist that are H-exact for the given H and achieve the stated lower bounds on f(H).
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper defines H-exact graphs G for a k-vertex graph H: every induced k-vertex subgraph of G is either isomorphic to H or incomparable to H (neither contains the other as a subgraph). It studies f(H), the maximum order of such a G, and proves several results on trees and matchings: for any tree T on k≥3 vertices, (k-1)(⌈k/2⌉−1) ≤ f(T) ≤ (k−1)^2; exact equality f(K_{1,k−1})=(k−1)(k−2) for k≥4; exact values f(P_k)=(k−1)^2/2 (k odd) and (k−1)(k−2)/2 +1 (k even) for k≥5; and f(nK_2)=3n (n=2,3) and 4n−4 (n≥4). The claims rest on explicit constructions achieving the lower bounds together with matching upper-bound arguments.
Significance. If the stated equalities and bounds hold, the work supplies concrete, verifiable determinations of the largest H-exact graphs for several infinite families, supported by direct constructions whose induced k-subgraphs are checked to be either H or incomparable. These results give precise extremal information in a setting that blends induced-subgraph restrictions with incomparability, which may connect to Ramsey-type questions as suggested by the title. The parameter-free nature of the bounds and the matching constructions are strengths.
minor comments (2)
- The definition of 'incomparable' (neither contains the other) should explicitly state whether containment is as an ordinary subgraph or induced subgraph; the surrounding text implies ordinary subgraphs, but a single clarifying sentence would remove ambiguity.
- The abstract states the four representative results without indicating the proof techniques (e.g., counting arguments or potential functions for the upper bounds); a brief parenthetical in the abstract or a short methods paragraph would improve readability.
Simulated Author's Rebuttal
We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. We are pleased that the definitions, bounds, and exact values for f(H) on trees and matchings were viewed favorably.
Circularity Check
No significant circularity; derivations are self-contained
full rationale
The paper defines f(H) directly from the Exact(H) property and derives the stated bounds and exact values via explicit graph constructions (for lower bounds) together with direct combinatorial arguments proving no larger order is possible (for upper bounds). These steps rely on the definitions of incomparability and induced subgraphs but do not reduce any claimed equality or bound to a fitted input, self-citation chain, or renaming of a prior result. The constructions are verified to satisfy the H-exact condition by inspection of all k-vertex induced subgraphs, making the results independent of the inputs by construction.
Assumptions & free parameters
assumptions (1)
- standard math Graphs are finite, simple, undirected; induced subgraphs and subgraph containment are the standard definitions from graph theory.
Cite this review
Pith. "Pith review of Induced/Incomparable versus Ramsey." pith.science (2026). https://pith.science/paper/CR2CR44D
@misc{pith2026260522077,
author = {Pith},
title = {Pith review of: Induced/Incomparable versus Ramsey},
year = {2026},
howpublished = {\url{https://pith.science/paper/CR2CR44D}},
note = {Machine review of arXiv:2605.22077}
}
abstract
We consider the following problem: Let $H$ and $F$ be two graphs on $k$ vertices and assume $F \neq H$. We say that $H$ and $F$ are incomparable if neither $F$ nor $H$ contains the other. Let $H$ be a graph on $k$ vertices and let $G$ be a graph on at least $k$ vertices. Then $G$ is said to be $H$-exact if any induced subgraph of $G$ on $k$ vertices is either isomorphic to $H$ or incomparable with $H$. Exact($H$) is the family of all graphs $G$ which are $H$-exact. We pose the following problem: For a graph $H$ on $k$ vertices, determine or estimate $f(H) = \max \{n: \exists G \in \text{Exact}(H), |V (G)| = n\}$. Among the many results obtained in this paper the following are representatives concerning trees and matchings: 1. For a tree on $k \geq 3$ vertices, $ (k - 1)(\left \lceil \frac{k}{2} \right \rceil -1 ) \leq f(T) \leq ( k-1)^2$. 2. For $k \geq 4$, $f(K_{1,k-1}) = (k-1)(k-2)$. 3. For $k \geq 5$, $f(P_k) = \frac{(k-1)^2}{2}$ if $k$ is odd and $f(P_k) = \frac{(k-1)(k-2)}{2}+1$ if $k$ is even. 4. $f(nK_2) = 3n$ for $n = 2, 3$ and $f(nK_2) = 4n - 4$ for $n \geq 4$.
Reference graph
Works this paper leans on
- [1]
-
[2]
Y. Caro. On graphs with prescribed subgraphs of orderkand a Theorem of Kelly and Merriell.Czechoslovak Mathematical Journal, 44(4):623–629, 1994
work page 1994
- [3]
-
[4]
V. Chv´ atal and F. Harary. Generalized Ramsey theory for graphs. iii. small off-diagonal numbers.Pacific Journal of Mathematics, 41:335–345, 1972
work page 1972
-
[5]
J.H. Kim. The Ramsey number R(3,t) has order of magnitudet 2/logt. Random Structures & Algorithms, 7(3):173–207, 1995
work page 1995
-
[6]
D. K˝ onig. Gr´ afok ´ es m´ atrixok.Matematikai ´ es Fizikai Lapok, 38:116–119, 1931
work page 1931
-
[7]
P.J. Lorimer and W. Solomon. The Ramsey numbers for stripes and complete graphs 1.Discrete Mathematics, 104(1):91–97, 1992
work page 1992
-
[8]
J. Spencer. Ramsey’s theorem—a new lower bound.Journal of Combi- natorial Theory, Series A, 18(1):108–115, 1975. 25
work page 1975
Reviewed June 30, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.