Recognition: 1 theorem link
· Lean TheoremA non-hereditary Pollyanna class that is not strongly Pollyanna
Pith reviewed 2026-05-15 01:23 UTC · model grok-4.3
The pith
A non-hereditary graph class exists that is Pollyanna but fails to be strongly Pollyanna for every k.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors construct a class C of graphs such that for every chi-bounded class F the intersection C cap F is polynomially chi-bounded, yet for every positive integer k there exists a k-good class F where C cap F is not polynomially chi-bounded; therefore C is Pollyanna but not k-strongly Pollyanna for any k and hence not strongly Pollyanna.
What carries the argument
The explicitly constructed non-hereditary class C that meets the Pollyanna intersection condition while violating the stronger k-good intersection condition for every k.
If this is right
- The Pollyanna and strongly Pollyanna properties are distinct when graph classes need not be hereditary.
- The open question of Chudnovsky, Cook, Davies, and Oum receives an affirmative answer under the literal non-hereditary reading.
- The distinction between the two notions can be witnessed by a single explicit class rather than by abstract existence.
Where Pith is reading between the lines
- If the same separation fails to hold inside hereditary classes, then heredity itself would become the key restriction separating the two properties.
- The construction technique may adapt to produce further examples separating other boundedness notions in graph classes.
- Checking whether every hereditary Pollyanna class is automatically strongly Pollyanna remains open after this result.
Load-bearing premise
Graph classes are permitted to be non-hereditary.
What would settle it
A demonstration that the constructed class C fails to satisfy the claimed intersection bounds for some chi-bounded or k-good family F.
read the original abstract
Chudnovsky, Cook, Davies, and Oum introduced the notion of Pollyanna graph classes: a class $\mathcal{C}$ is Pollyanna if for every $\chi$-bounded class $\mathcal{F}$, the intersection $\mathcal{C} \cap \mathcal{F}$ is polynomially $\chi$-bounded. They further defined $\mathcal{C}$ to be strongly Pollyanna if it is $k$-strongly Pollyanna for some integer $k$, meaning that $\mathcal{C} \cap \mathcal{F}$ is polynomially $\chi$-bounded for every $k$-good class $\mathcal{F}$. They asked whether there are Pollyanna graph classes that are not strongly Pollyanna. In this note we answer this question affirmatively, under the literal interpretation that graph classes are not required to be hereditary. We construct a class $\mathcal{C}$ that is Pollyanna but, for every $k \ge 1$, is not $k$-strongly Pollyanna; in particular $\mathcal{C}$ is not strongly Pollyanna.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript constructs an explicit non-hereditary graph class C that is Pollyanna (its intersection with any χ-bounded class F is polynomially χ-bounded) but fails to be k-strongly Pollyanna for every k ≥ 1 (there exists a k-good F such that C ∩ F is not polynomially χ-bounded). This affirmatively answers the open question of Chudnovsky, Cook, Davies, and Oum under the literal reading that graph classes need not be hereditary.
Significance. The construction separates the Pollyanna and strongly Pollyanna properties via a non-hereditary class, directly resolving the question posed in the literature. The explicit nature of the class and its verification against the supplied definitions is a strength, as it permits straightforward checking without additional assumptions on closure properties.
Simulated Author's Rebuttal
We thank the referee for their positive assessment of the manuscript and their recommendation to accept. The report accurately summarizes our explicit construction of a non-hereditary graph class that is Pollyanna but not strongly Pollyanna, thereby resolving the question of Chudnovsky, Cook, Davies, and Oum under the literal (non-hereditary) interpretation of graph classes.
Circularity Check
No significant circularity
full rationale
The paper answers an open question by exhibiting an explicit non-hereditary graph class C that meets the definition of Pollyanna (every intersection with a χ-bounded class is polynomially χ-bounded) yet fails to be k-strongly Pollyanna for every k. The construction is built directly from the supplied definitions of the two properties and the explicit permission that classes need not be hereditary; no parameter is fitted, no quantity is renamed as a prediction, and no load-bearing step reduces to a self-citation or prior result by the same authors. The derivation is therefore self-contained against the external definitions.
Axiom & Free-Parameter Ledger
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We construct a class C that is Pollyanna but, for every k ≥ 1, is not k-strongly Pollyanna
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
-
[1]
M. Bria´ nski, J. Davies and B. Walczak, Separating polynomialχ-boundedness fromχ- boundedness,Combinatorica44(2024), 1–8
work page 2024
-
[2]
M. Chudnovsky, L. Cook, J. Davies and S. Oum, Reunitingχ-boundedness with polynomial χ-boundedness,J. Combin. Theory Ser. B176(2026), 30–73. 6
work page 2026
-
[3]
L. Esperet, Graph colorings, flows and perfect matchings, Habilitation Thesis, Universit´ e Grenoble Alpes, 2017
work page 2017
-
[4]
A. Gy´ arfas, On Ramsey covering-numbers, in:Infinite and Finite Sets (Colloq., Keszthely, 1973; Dedicated to P. Erd˝ os on His 60th Birthday), vol. II, Colloq. Math. Soc. J´ anos Bolyai 10(1975), 801–816
work page 1973
-
[5]
Erd˝ os, Graph theory and probability,Canad
P. Erd˝ os, Graph theory and probability,Canad. J. Math.11(1959), 34–38
work page 1959
-
[6]
Mycielski, Sur le coloriage des graphs,Colloq
J. Mycielski, Sur le coloriage des graphs,Colloq. Math.3(1955), 161–162
work page 1955
-
[7]
A. A. Zykov, On some properties of linear complexes,Mat. Sb. N.S.24(66)(1949), 163–188. 7
work page 1949
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.