Induced/Incomparable versus Ramsey

Christina Zarb; Yair Caro; Zsolt Tuza

arxiv: 2605.22077 · v2 · pith:CR2CR44Dnew · submitted 2026-05-21 · 🧮 math.CO

Induced/Incomparable versus Ramsey

Yair Caro , Zsolt Tuza , Christina Zarb This is my paper

Pith reviewed 2026-05-22 04:49 UTC · model grok-4.3

classification 🧮 math.CO

keywords extremal graph theoryinduced subgraphsincomparable graphstreespathsstarsmatchingsRamsey-type problems

0 comments

The pith

For k at least 4, the largest graph where every induced k-subgraph is a star or incomparable to it has exactly (k-1)(k-2) vertices.

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

The paper introduces the extremal function f(H) for a graph H on k vertices: the largest n such that some graph G on n vertices has every induced k-vertex subgraph either isomorphic to H or incomparable to H, meaning neither contains the other as a subgraph. They obtain exact values for several families, including stars, paths, and matchings of edges, along with general bounds that apply to all trees. These determinations give concrete maximum sizes and constructions that refine the possible scale of such restricted graphs.

Core claim

The authors prove that for k greater than or equal to 4, f(K_{1,k-1}) equals (k-1)(k-2). For k greater than or equal to 5, f(P_k) equals (k-1)/2 when k is odd and (k-1)(k-2)/2 plus 1 when k is even. For the matching consisting of n disjoint edges, f(nK_2) equals 3n when n equals 2 or 3, and equals 4n minus 4 when n is at least 4. For any tree T on k vertices they also show the general sandwich (k-1)(ceil(k/2) minus 1) is less than or equal to f(T) which is less than or equal to (k-1) squared.

What carries the argument

The extremal function f(H), defined as the maximum number of vertices in an H-exact graph where every induced subgraph on k vertices is isomorphic to H or incomparable with H.

If this is right

For every tree on k vertices, f(T) satisfies the inequality (k-1)(ceil(k/2)-1) less than or equal to f(T) less than or equal to (k-1) squared.
The exact formulas for stars achieve the general upper bound in that special case.
The values for paths and matchings give tight constructions that realize the largest possible graphs under the exactness condition.

Where Pith is reading between the lines

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

The same approach could be used to compute or bound f(H) for other specific families such as cycles or complete bipartite graphs.
Constructions achieving these maxima might serve as building blocks for larger graphs with controlled induced-subgraph diversity.
The parameter f(H) offers a way to quantify how large a graph can be while forbidding certain mixtures of induced copies.

Load-bearing premise

Incomparability is defined by neither graph containing the other as a subgraph, and attention is restricted to induced subgraphs on exactly k vertices with H different from the other graph.

What would settle it

A graph on more than (k-1)(k-2) vertices for k at least 4 in which every induced k-vertex subgraph is either the star K_{1,k-1} or incomparable to it would show that the claimed exact value for stars is not the maximum.

read the original 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$.

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

The path formulas contradict the setup since f(P_k) falls below k while any H-exact graph must have at least k vertices.

read the letter

The paper introduces the notion of an H-exact graph: on at least k vertices, every induced k-vertex subgraph is either isomorphic to H or incomparable to it (neither contains the other as a subgraph). It defines f(H) as the largest possible order of such a graph and supplies bounds plus some exact values for trees, stars, paths, and matchings. That definition and the function f(H) are new, and the concrete numbers for stars and small matchings look like they could be useful if the proofs hold. The general tree bound of (k-1)(ceil(k/2)-1) to (k-1)^2 is a reasonable first estimate in this corner of induced extremal problems. The star result f(K_{1,k-1}) = (k-1)(k-2) for k >= 4 is stated cleanly and sits above k, so it does not immediately clash with the setup. The matching results for n=2,3 and n>=4 also stay large enough to be plausible. The path claims, however, do not. For odd k >=5 the paper states f(P_k) = (k-1)/2; at k=5 this is 2. But the definition requires |V(G)| >=k to make the induced-subgraph condition meaningful, and even a vacuous reading for smaller orders only pushes the maximum up to at least k-1. A graph on exactly k vertices that is itself a copy of P_k satisfies the condition directly, so f(P_k) cannot be smaller than k. This is an internal contradiction, not a minor slip. The even-k path formula is larger but inherits the same definitional tension. Because the abstract alone already flags the inconsistency and the full text repeats the same numbers, the central results for paths cannot be trusted without major revision. The work targets specialists who track induced-subgraph restrictions in small graphs. A reader looking for quick numerical values on stars or matchings might extract something, but anyone checking the path section will hit the same mismatch. I would not send this to peer review in its current form; the error is load-bearing and needs fixing first.

Referee Report

1 major / 0 minor

Summary. The paper defines H-exact graphs G on n ≥ k vertices such that every induced k-vertex subgraph is isomorphic to a fixed H on k vertices or incomparable to H (neither contains the other as a subgraph). It investigates the extremal function f(H), the largest possible n for which an H-exact G exists, and derives bounds for trees together with exact values for stars, paths, and matchings.

Significance. If the results hold, the work contributes concrete exact values in an induced-subgraph analogue of Ramsey problems, notably the parameter-free determinations f(K_{1,k-1}) = (k-1)(k-2) and the piecewise formula for f(nK_2). These provide falsifiable combinatorial predictions for specific families.

major comments (1)

[Abstract] Abstract, representative result 3: the exact claim f(P_k) = (k-1)/2 for odd k ≥ 5 (e.g., f(P_5) = 2) is strictly smaller than k. By the definition in the opening setup, Exact(H) consists solely of graphs on at least k vertices, so any admissible n satisfies n ≥ k and f(H) cannot be smaller than k. This internal inconsistency is load-bearing for the path results.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the inconsistency in the claimed value of f(P_k) for odd k. We agree this requires correction and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Abstract] Abstract, representative result 3: the exact claim f(P_k) = (k-1)/2 for odd k ≥ 5 (e.g., f(P_5) = 2) is strictly smaller than k. By the definition in the opening setup, Exact(H) consists solely of graphs on at least k vertices, so any admissible n satisfies n ≥ k and f(H) cannot be smaller than k. This internal inconsistency is load-bearing for the path results.

Authors: We agree with the referee that the stated formula for f(P_k) when k is odd produces a value strictly less than k, which contradicts the definition of Exact(H) and the fact that f(H) ≥ k holds for any H (as H itself is H-exact). This indicates an error in our analysis of paths. In the revised manuscript we will remove or correct the incorrect formula for odd k, ensure all stated values of f(P_k) satisfy the lower bound n ≥ k, and update the abstract to reflect only valid results. We will also re-examine the full path section to confirm consistency with the definition. revision: yes

Circularity Check

0 steps flagged

No circularity; claims rest on independent combinatorial arguments

full rationale

The abstract states definitions of incomparability and Exact(H) for graphs on at least k vertices, then lists explicit bounds and exact values for f(T), f(K_{1,k-1}), f(P_k), and f(nK_2) as representative results. No equations, fitted parameters, or self-citations are exhibited that reduce any claimed f(H) value to a quantity defined from the same result or prior author work. The derivation chain is not shown to collapse by construction; the results are presented as obtained from direct analysis of induced subgraphs and incomparability conditions. The noted discrepancy between f(P_k)=(k-1)/2 for odd k and the |V(G)|>=k requirement is a potential correctness or vacuous-case issue, not a circular reduction. This is the normal case of a self-contained combinatorial paper with no load-bearing self-reference or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the newly introduced definition of H-exact graphs together with standard notions of induced subgraphs and subgraph containment from classical graph theory; no free parameters or invented entities appear in the abstract.

axioms (1)

standard math Standard definitions of undirected graphs, induced subgraphs, and subgraph containment hold.
The problem statement and all results presuppose these conventional background facts without re-deriving them.

pith-pipeline@v0.9.0 · 5909 in / 1265 out tokens · 70840 ms · 2026-05-22T04:49:44.231664+00:00 · methodology

Induced/Incomparable versus Ramsey

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)