pith. sign in

arxiv: 2509.09035 · v3 · pith:NRHWE4H3new · submitted 2025-09-10 · 🧮 math.CO · math.MG

Asymptotic structure. III. Excluding a fat tree

classification 🧮 math.CO math.MG
keywords everygraphfinitetreeminorthereline-widthpath-width
0
0 comments X
read the original abstract

Robertson and Seymour proved that for every finite tree $H$, there exists $k$ such that every finite graph $G$ with no $H$ minor has path-width at most $k$; and conversely, for every integer $k$, there is a finite tree $H$ such that every finite graph $G$ with an $H$ minor has path-width more than $k$. If we (twice) replace ``path-width'' by ``line-width'', the same is true for infinite graphs $G$. We prove a ``coarse graph theory'' analogue, as follows. For every finite tree $H$ and every $c$, there exist $k,L,C$ such that every graph that does not contain $H$ as a $c$-fat minor admits an $(L,C)$-quasi-isonetry to a graph with line-width at most $k$; and conversely, for all $k,L,C$ there exist $c$ and a finite tree $H$ such that every graph that contains $H$ as a $c$-fat minor admits no $(L,C)$-quasi-isometry to a graph with line-width at most $k$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. A coarse Menger's Theorem for planar and bounded genus graphs

    math.CO 2026-05 unverdicted novelty 7.0

    In planar and bounded-genus graphs, absence of k pairwise d-far S-T paths implies a vertex set of size f(d,k) whose d-neighborhood intersects every S-T path.