Pith. sign in

REVIEW 1 cited by

Equivalence between Erd\H{o}s-Hajnal and polynomial R\"odl and Nikiforov conjectures

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2403.08303 v2 pith:FCFSH7QZ submitted 2024-03-13 math.CO

classification math.CO
keywords graphsnguyenpolynomialscottseymourconjectureconjecturesnikiforov
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

It is well-known that polynomial versions of theorems of R\"odl and Nikiforov, as conjectured by Fox and Sudakov and Nguyen, Scott and Seymour imply the classical Erd\H{o}s-Hajnal conjecture. In this note, we prove that these three conjectures are in fact equivalent, extending several previous particular results in this direction by Fox, Nguyen, Scott and Seymour; Nguyen, Scott and Seymour and Gishboliner and Shapira. We deduce that the family of string graphs satisfies the polynomial R\"odl conjecture. We also derive analogous results for hypergraphs, tournaments, ordered graphs, and colored graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Regularity for hypergraphs with bounded VC$_2$ dimension

    math.CO 2025-08 accept novelty 8.0 of 10

    For 3-graphs of bounded VC2 dimension, an (ε,ψ)-regular partition exists with twr(twr(poly(1/ε))) vertex parts, improving the generic wowzer bound to tower type.

Pith tools