PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Tight(er) Bounds for the Excluded Grid Theorem

Julia Chuzhoy, Zihan Tan

arXiv:1901.07944v1cs.DM

TL;DR

The Excluded Grid Theorem asks how much treewidth is needed to guarantee a grid minor, and tighter bounds matter for algorithms and graph-theoretic results. This paper develops a crossbar-based proof framework and establishes a polynomial upper bound of order g^9 times a polylogarithmic factor. The authors describe the framework as simpler than previous proofs and suggest it may permit tighter bounds.

  • Problem

    The open question is to tighten f(g), the minimum treewidth threshold that guarantees a g × g grid minor; better upper bounds affect algorithm running times and graph-theoretic parameters.

    Source: §1 · p. 2

  • Method

    The proof transforms a Path-of-Sets System into a hairy version and uses a crossbar-or-Path-of-Sets dichotomy to obtain grid-containing structures.

    Source: §1 · p. 4

  • Results

    For every g ≥ 2, treewidth at least c1g^9 log^c2 g guarantees a (g × g)-grid minor.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors describe their framework as significantly simpler than previous proofs and say it may lead to tighter bounds on f(g).

    Source: §1 · p. 2

    The stated path-intersection stage assumes D ≤ N ≤ Dg^2 disjoint paths, with D = 64g^4, and uses M = 8g^4 log g slices.

    Source: §4.3 · p. 20

Abstract

from arXiv · show

We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f: \mathbb{Z}^+ \to \mathbb{Z}^+$, such that for every integer $g>0$, every graph of treewidth at least $f(g)$ contains the $(g\times g)$-grid as a minor. For every integer $g>0$, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that $f(g)=\Omega(g^2\log g)$ must hold. For a long time, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g)=O(g^{98}\text{poly}\log g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36}\text{poly} \log g)$, and then to $f(g)=O(g^{19}\text{poly}\log g)$. In this paper we further improve this bound to $f(g)=O(g^{9}\text{poly} \log g)$. We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on $f(g)$.

1 Introduction

The paper improves the Excluded Grid Theorem’s treewidth upper bound and introduces a crossbar-based approach intended to simplify proofs and leave room for tighter bounds. Its main result guarantees a g × g grid minor once treewidth is at least c1g^9 log^c2 g.

1 Introduction

  • The Excluded Grid Theorem asks how large treewidth must be to force a grid minor; improved upper bounds affect algorithm running times and graph-theoretic parameters.Robertson et al. established the lower bound f(g) = Ω(g^2 log g).Source: §1 · p. 2
  • Earlier bounds progressed from O(g^98 poly log g) to O(g^36 poly log g) and O(g^19 poly log g), while the paper claims a significantly simpler framework.The authors note that the previous O(g^19 poly log g) proof was an 80-page manuscript.Source: §1 · p. 2
  • For every g ≥ 2, treewidth at least c1g^9 log^c2 g guarantees a (g × g)-grid minor.This is the paper’s stated upper bound for the threshold f(g).Source: §1 · p. 2
  • Earlier length-doubling approaches lose a factor c per iteration, making that loss critical to the resulting bound and, in the authors’ view, unlikely to yield tight bounds.The approach requires roughly 2 log g iterations to reach length g^2; the stated best loss estimate is roughly 2^15.Source: §1 · p. 4
  • The approach starts from a Path-of-Sets System of length Θ(log k) and width k / poly log k, then transforms it into a hairy system with additional linked clusters.The transformation splits each original cluster and adds w node-disjoint paths connecting the resulting cluster to its corresponding S_i cluster.Source: §1 · p. 4
  • The proof introduces crossbars: structures used to derive either a grid-producing Path-of-Sets System or an expander minor that contains the grid.If a cluster lacks a crossbar, its minor contains a Path-of-Sets System of length and width Ω(g^2); otherwise, crossbars yield an expander on Ω(g^2) vertices with maximum degree O(log g).Source: §1 · pp. 4–5

2 Preliminaries

The preliminaries define treewidth, grid minors, and well-linked vertex sets, then introduce Path-of-Sets and hairy Path-of-Sets Systems used in the paper. They also state conditions under which these structures yield grid minors or can be found in graphs of large treewidth.

Treewidth, Minors and Grids

  • Treewidth is the minimum, over tree-decompositions, of the largest bag size minus one; the largest node-well-linked vertex set has size within constant factors of treewidth.The stated bounds are |T|/4 −1 and |T| −1.Source: §2 · pp. 5–6
  • A graph minor is represented by disjoint connected vertex subgraphs and internally disjoint edge paths, while a grid minor is a minor isomorphic to the defined square grid.The grid has horizontal and vertical edges between neighboring vertices.Source: §2 · pp. 5–6

Path-of-Sets System

  • A Path-of-Sets System links disjoint clusters in sequence with node-disjoint paths, using two size-w terminal sets in each cluster.A strong system additionally requires each terminal set to be node-well-linked and the two sets to be linked within their cluster.Source: §2 · p. 6
  • A strong Path-of-Sets System of length and width g^2 contains a grid minor of side ⌊g/c⌋ for a constant c ≥ 1.The stated theorem applies for integers g ≥ 2.Source: §2 · p. 6

Hairy Path-of-Sets System

  • A hairy Path-of-Sets System adds a cluster S_i to each cluster C_i, joined by w node-disjoint paths whose endpoints satisfy well-linkedness conditions.The definition includes a strong Path-of-Sets System, sets X_i and Y_i, and connecting paths Q_i.Source: §2 · p. 7
  • If k/log^c′ k > c wℓ^48, every graph of treewidth at least k contains a maximum-degree-3 subgraph with a hairy Path-of-Sets System of length ℓ and width w.The theorem holds for constants c, c′ > 0 and integers ℓ, w, k > 1.Source: §2 · p. 7

3 Proof of the Excluded Grid Theorem

The proof introduces crossbars and uses them, together with strong Path-of-Sets Systems, to derive grid minors. Its route combines a cut-matching-game expander construction with separator-based arguments and yields the stated treewidth bound.

3 Proof of the Excluded Grid Theorem

  • A crossbar consists of disjoint A-to-B paths, each linked to X by a path, with the specified disjointness conditions.The theorem’s definition calls the number of A-to-B paths the crossbar’s width.Source: §3 · p. 8
  • If the crossbar alternative fails, Theorem 3.1 produces a minor containing a strong Path-of-Sets System of length and width Ω(g^2).The alternative is an (A, B, X)-crossbar of width g^2, under the theorem’s stated size and path assumptions.Source: §3 · p. 8
  • The proof develops a simpler, slightly weaker version requiring κ = Ω(g^10 log g), then gives the full proof of Theorem 3.1.The weaker version leads to f(g) = O(g^10 poly log g); the final argument converts its intermediate treewidth condition into the stated threshold using polylogarithmic factors in g.Source: §3 · pp. 8–9
  • When g ≥ 2 is an integral power of 2 and each odd i from 1 through ℓ has an (Ai, Bi, Yi)-crossbar of width g² in Ci ∪ Qi, G contains a grid minor of side g′ = Ω(g / log^1.5 g).Source: §3 · p. 8
  • The 1/2-expander minor has g^2 vertices and degree O(log g); separator bounds then imply that it contains a grid minor.The proof bounds separator size using expansion and maximum degree, then applies a separator-or-minor theorem to obtain the grid minor.Source: §3 · pp. 9, 11
  • The proof embeds a cut-matching-game expander into the graph, and the game yields a 1/2-expander after ⌈γ_CMG log N⌉ iterations with high probability.The cut player’s strategy is adaptive, and the resulting expander’s maximum degree equals the number of iterations.Source: §3 · p. 10

4 Building the Crossbar

This section develops a simpler proof framework for a weaker version of Theorem 3.1, building a crossbar-or-pseudo-grid alternative and slicing paths to construct and strengthen a weak path-of-sets system. Along the way, it extracts intersecting path sets, decomposes them into well-linked clusters, and selects indices with large consecutive overlaps.

4 Building the Crossbar

  • The weaker proof assumes κ ≥ 222g10 log g and provides a simpler framework containing the main ideas and machinery for the full proof of Theorem 3.1.This weaker theorem immediately gives f(g) = O(g^10 poly log g); the full proof is completed in Section 5.Source: §4 · p. 12

4.1 Step 1: Pseudo-Grid

  • For 1 ≤ D ≤ κ/(2g^2), either H contains an (A, B, X)-crossbar of width g^2 or a pseudo-grid of depth D.A pseudo-grid uses disjoint path subsets of size at most g^2 and a large family of paths that intersect nearly every subset.Source: §4.1 · p. 13

4.2 Step 2: Slicing the Paths of R

  • If perfect unique linkage holds and |Q| ≥ M w + (M + 1)N, an M-slicing exists with width w relative to Q.Before slicing, the construction retains at least κ/8 paths intersecting every pseudo-grid layer and contracts the graph to preserve that property while making the linkage perfect and unique.Source: §4.2 · pp. 15–17
  • With |Q| ≥ M w + (M + 1)N, the iterative procedure produces a valid M-slicing of width at least w.The slicing is constructed over M − 1 iterations.Source: §4.2 · p. 18

4.3 Step 3: Intersecting Path Sets

  • If each Q intersects at least 2D paths of R and |Q| ≥ 2|R|w/D, a partition yields (w, D)-intersecting R′ and Q′ with |Q′| ≥ |Q|/2.Every path in R′′ intersects at most w paths of Q′.Source: §4.3 · p. 19

4.4 Step 4: Well-Linked Decomposition

  • For (4w, 2D)-intersecting path sets with D ≥ 8w, Theorem 4.11 yields disjoint happy clusters containing a selected subset Σ′ of paths.In the application, each slice yields a cluster with at least D/4 segments whose endpoints are g²-weakly well-linked.Source: §4.4 · pp. 21–22

4.5 Step 5: Constructing a Weak Path-of-Sets System

  • Under N ≥ 3w, D² ≥ 4Nw, and MD ≥ 2Nw, there are w increasing indices whose consecutive sets overlap in at least w elements.The step uses this selection result to construct a weak Path-of-Sets System of width and length g² in H′′, whose maximum vertex degree is at most 4.Source: §4.5 · p. 22
  • A set-overlap DAG yields a directed path selecting g^2 clusters with consecutive overlaps of at least g^2, forming a weak path-of-sets system of length and width g^2.The construction uses paths connecting the endpoint sets of consecutive clusters.Source: §4.5 · pp. 23, 25, §4.6 · p. 25

4.6 Step 6: a Strong Path-of-Sets System

  • The weak system is converted into a strong path-of-sets system of length g^2 and width Ω(g^2), using well-linked endpoint subsets and linked paths between clusters.The new system retains the same clusters, while its width decreases by a constant factor.Source: §4.6 · pp. 25–26

4.7 Parameters

  • After well-linked decomposition, there are 8g^4 log g clusters, each with at least D/4 segments whose endpoints are g^2-weakly well-linked.The pseud-grid depth is D = 64g^4.Source: §4.7 · p. 27

5 Proof of Theorem 3.1

The proof seeks either an (A, B, X)-crossbar of width g^2 or a strong Path-of-Sets System with length and width both Ω(g^2). It adapts the earlier framework to save a factor of g in κ.

5 Proof of Theorem 3.1

  • The target is an (A, B, X)-crossbar of width g^2 or a strong Path-of-Sets System with length and width at least Ω(g^2).The input includes disjoint sets A, B, X of size κ ≥ 2^22 g^9 log g and path families connecting A to B and A to X.Source: §5 · p. 27
  • The proof follows the Section 4 framework with changes that save a factor of g on κ.The first three steps are identical apart from using slightly weaker slicing parameters.Source: §5 · p. 27

Step 1: Pseudo-Grid

  • Step 1 applies Theorem 4.1, returning a width-g^2 crossbar if found and otherwise obtaining a pseudo-grid of depth D = 64g^4.The pseudo-grid has D ≤ N ≤ g^2D, where N = |R|.Source: Step 1: Pseudo-Grid · p. 27

Step 2: Slicing

The slicing step retains paths that intersect every row of the pseudo-grid, then modifies the graph while preserving key linkage properties. It obtains fewer slices than the earlier proof by a factor of g.

Step 2: Slicing

  • At most 2g^2D paths are discarded, leaving |Q′′| ≥ κ/8 paths that each intersect every R_i.The bound follows by discarding paths that miss at least one row.Source: Step 2: Slicing · p. 27
  • The graph is modified to a minor H′′ while preserving property I1 and the perfect unique linkage property with linkage R.The linkage is with respect to A′ and B′.Source: Step 2: Slicing · p. 27
  • The slicing yields M1 = 128g^3 log g slices of width w = 2^11g^6, a factor g fewer slices than in Section 4.The stated bounds on N and |Q′′| satisfy the condition for applying Theorem 4.5.Source: Step 2: Slicing · p. 28

Step 3: Intersecting Path Sets

The proof applies a path-set lemma to each slice and then splits into two cases based on how many slices have large Σ′_i sets. Case 1 has fewer slices but large sets in many of them; Case 2 can increase the slice count.

Step 3: Intersecting Path Sets

  • Applying Lemma 4.8 to a slice yields a (4g^2, D/2)-intersecting pair, with |Q′_i| ≥ 2^10g^6 and each path of Σ′′_i intersecting at most 4g^2 paths of Q′_i.The application uses parameters 4g^2 and D/2.Source: Step 3: Intersecting Path Sets · p. 28
  • Slices are divided by whether |Σ′_i| ≥ N/g; Case 1 has at least half type-1 slices, while Case 2 has fewer than half.The proof aims to compensate for fewer slices in Case 1 with larger Σ′_i sets, and to increase the slice count in Case 2.Source: Step 3: Intersecting Path Sets · p. 28

5.1 Case 1: Many Type-1 Slices

In Case 1, the proof keeps only type-1 slices, retaining at least half the slices while ensuring each retained slice has |Σ′_i| ≥ N/g.

5.1 Case 1: Many Type-1 Slices

  • Case 1 retains 64g^3 log g type-1 slices, each with |Σ′_i| ≥ N/g.All type-2 slices are ignored.Source: §5.1 · p. 28
  • The retained path sets (Σ′_i, Q′_i) are stated to be (4g^2, D/2)-intersecting.Source: §5.1 · p. 28

Step 4: Well-Linked Decomposition

The decomposition balances the number of clusters against the size of their path sets. Geometric grouping identifies a class with many paths, while retaining clusters whose path endpoints are well-linked.

Step 4: Well-Linked Decomposition

  • The resulting path sets have well-linked endpoints within their clusters and collectively contain at least M1N/(4g) paths.These guarantees hold for the selected happy clusters across type-1 slices.Source: Step 4: Well-Linked Decomposition · pp. 28–29
  • Geometric grouping addresses the tradeoff between having many clusters and having large path sets in each cluster.The path-set sizes range from D/4 to N, with N at most g^2D.Source: Step 4: Well-Linked Decomposition · pp. 28–29
  • Geometric classes yield a cluster collection with at least 8Ng^2/(D·2^j) clusters, each having at least D·2^j/4 paths.The selected class contains at least M1N/(16g log g) paths.Source: Step 4: Well-Linked Decomposition · p. 29

Step 5: a Path-of-Sets System

The selected clusters and their sets S_i are used with Theorem 4.15 to build a weak Path-of-Sets System, which is then converted into a strong one.

Step 5: a Path-of-Sets System

  • Clusters are ordered by slice, and clusters from the same slice have disjoint associated sets S_i.This ordering supports the selection of g^2 clusters, each from a different slice.Source: Step 5: a Path-of-Sets System · p. 29
  • The parameters satisfy the three conditions required by Theorem 4.15.The proof checks ˆN ≥ 3ˆw, ˆD^2 ≥ 4ˆNˆw, and ˆDˆM ≥ 2ˆNˆw.Source: Step 5: a Path-of-Sets System · p. 29
  • The construction produces a strong Path-of-Sets System of width g^2 and length g^2.Theorem 4.15 first yields the weak system; the proof then applies the established conversion procedure.Source: Step 5: a Path-of-Sets System · p. 29

5.2 Case 2: Many Type-2 Slices

In Case 2, the proof either finds a crossbar or builds a sufficiently wide slicing from type-2 slices. The resulting construction supports a strong Path-of-Sets System of length and width Ω(g^2).

5.2 Case 2: Many Type-2 Slices

  • Without a width-g^2 crossbar, Theorem 5.1 provides 8g^4 log g slices of width at least N/g.This is the stated slicing guarantee for Case 2.Source: §5.2 · p. 30
  • For a type-2 slice, Lemma 5.2 constructs a slicing into g parts with width at least N/g.Paths intersecting the ignored subset are removed before the slicing is extended to the original slice.Source: §5.2 · pp. 30–31
  • At least 64g^3 log g type-2 slices can each be subdivided into g slices, giving more than 8g^4 log g slices of width at least N/g.The subdivision uses Lemma 5.2 and combines the resulting individual slicings with the original slicing.Source: §5.2 · p. 30
  • An iterative construction using paths from B2 and Σ′′_i builds a width-g^2 crossbar when enough disjoint paths are available.Each iteration adds a path and its corresponding subpath while preserving disjointness invariants.Source: §5.2 · pp. 30–31
  • Repeating the earlier construction steps from the resulting slicing yields a strong Path-of-Sets System of length and width Ω(g^2).The proof reuses Steps 4–6 with the same D and N parameters.Source: §5.2 · p. 32

5.3 Parameters

The parameter summary records the scale of the pseudo-grid, its slicings, and the path subsets used in both cases.

5.3 Parameters

  • The pseudo-grid depth is D = 64g^4, with D path sets of at most g^2 paths each and a total of 64g^4 ≤ N ≤ 64g^6 paths.The original vertex sets have cardinality κ ≥ 2^22g^9 log g.Source: §5.3 · p. 32
  • The first slicing has M1 = 128g^3 log g slices and width w = 2^11g^6.For each slice, the summary also specifies subsets Σ′_i and Q′_i.Source: §5.3 · p. 32
  • The second slicing has M2 = 8g^4 log g slices and width w2 = N/g.The subsets in both cases form (4g^2, D/2)-intersecting path sets.Source: §5.3 · p. 32

A.1 Proof of Claim 2.2

Claim 2.2 is proved by building, for each pair of neighboring odd-indexed clusters, a disjoint path set through the intervening cluster.

A.1 Proof of Claim 2.2

  • For each 1 ≤ i < ⌈ℓ/2⌉, construct w′ node-disjoint paths from B′₂ᵢ₋₁ to A′₂ᵢ₊₁ within P₂ᵢ₋₁ ∪ C₂ᵢ ∪ P₂ᵢ.The sets of paths must be mutually disjoint and internally disjoint from the odd-indexed clusters.Source: §A.1 · p. 34
  • In C₂ᵢ, link the endpoints Ẋ ⊆ A₂ᵢ and Ŷ ⊆ B₂ᵢ of the paths entering from P₂ᵢ₋₁ and leaving through P₂ᵢ.The proof uses that (A₂ᵢ, B₂ᵢ) are linked in C₂ᵢ.Source: §A.1 · p. 34
  • Combining the incoming paths, the C₂ᵢ linkage Q, and the outgoing paths yields the required w′ paths between B′₂ᵢ₋₁ and A′₂ᵢ₊₁.The three path sets are ˜P₁, Q, and ˜P₂.Source: §A.1 · p. 34

A.2 Proof of Theorem 2.3

The proof starts with a strong Path-of-Sets System and converts it into a hairy one using degree reduction and a cluster-splitting theorem. The conversion halves length and reduces width by a constant factor.

A.2 Proof of Theorem 2.3

  • A graph of treewidth k has a subgraph G′ of maximum degree 3 and treewidth Ω(k/ poly log k).This is Theorem A.1, attributed to [CC15].Source: §A.2 · p. 34
  • If k/log^ĉ′ k > ĉwℓ⁴⁸, every graph of treewidth at least k contains a strong Path-of-Sets System of length ℓ and width w.This is Theorem A.2, attributed to.Source: §A.2 · p. 35
  • Theorem A.3 splits a cluster into disjoint clusters C′ and S′ while retaining at least κ/cΔ disjoint connecting paths and large linked subsets.It requires maximum degree at most Δ, equal-sized node-well-linked sets A and B, and A and B node-linked in the graph.Source: §A.2 · p. 35
  • A strong Path-of-Sets System of length ℓ′ and width w′ yields a hairy Path-of-Sets System of length at least ℓ′/2 and width at least w′/(3cΔ).Lemma A.4 applies when the graph has maximum vertex degree 3.Source: §A.2 · p. 35
  • The construction applies the cluster-splitting theorem to odd-indexed clusters, then links across each intervening even cluster to form a shorter Path-of-Sets System.The resulting system has length ⌈ℓ′/2⌉ and width ⌈w′/(3cΔ)⌉ before the final hairy-system construction.Source: §A.2 · p. 36

B Proof of Lemma 4.6

The proof builds a directed acyclic graph from a linkage and orders its vertices to define separators. It uses uniqueness of the linkage to rule out alternative reroutings and paths across those separators.

B Proof of Lemma 4.6

  • The auxiliary directed graph G′ has type-1 edges along linkage paths and type-2 edges defined by witnessed edges between distinct paths.An edge (v, v′) of type 2 is included when a later vertex on v’s path is adjacent to v′ in Ĝ.Source: B Proof of Lemma 4.6 · p. 36
  • G′ is acyclic: a shortest directed cycle cannot contain two vertices from the same linkage path, since Observation B.1 would give a shorter cycle.The proof then uses the distinct-path property to derive a contradiction from the minimal cycle.Source: B Proof of Lemma 4.6 · pp. 36–37
  • Every vertex of a shortest directed cycle lies on a distinct linkage path, enabling a cyclic rerouting that contradicts uniqueness of the original linkage.The rerouting joins each path prefix to a witness edge and the preceding path’s suffix.Source: B Proof of Lemma 4.6 · p. 37
  • A topological ordering of G′ defines a bijection μ that increases along each linkage path.The construction repeatedly removes a vertex with no incoming edges; such a vertex exists because G′ is acyclic.Source: B Proof of Lemma 4.6 · pp. 37–38
  • The separator Sₜ contains the first vertex on each linkage path with μ-value at least t, or that path’s last vertex if none qualifies.The proof rules out a path in Ĝ \ Sₜ between Yₜ and Zₜ by deriving a different linkage or a contradiction to the ordering.Source: B Proof of Lemma 4.6 · p. 38
Loading 1901.07944v1…