Pith. sign in

REVIEW 1 cited by

Long induced paths in $K_{s, s}$-free graphs

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 2411.19173 v2 pith:VRGMVVDM submitted 2024-11-28 math.CO

classification math.CO
keywords pathfreeinducedgraphsinftylengthraymondvertex
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$-free graph containing an $n$-vertex path must contain an induced path of length $f(n)$, where $f(n)\to \infty$ as $n\to \infty$. Recently, it was shown by Duron, Esperet and Raymond that one can take $f(n)=(\log \log n)^{1/5-o(1)}$. In this note, we give a short self-contained proof that a $K_{s, s}$-free graphs with an $n$-vertex path contains an induced path of length at least $(\log \log n)^{1-o(1)}$. Combined with the recent remarkable example of Cou\"etoux, Defrain, and Raymond, which provides an upper bound of $O((\log \log n)^{1+o(1)})$, this essentially resolves this old problem.

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. Graph classes through the lens of logic

    math.CO 2025-01 accept novelty 2.0 of 10

    A survey presenting first-order transductions as a unifying lens for graph classes, connecting sparsity, twin-width, and monadic stability and dependence.

Pith tools