pith. sign in

arxiv: 2512.18480 · v3 · submitted 2025-12-20 · 🧮 math.CO

Canonical tree-decompositions of chordal graphs

Raphael W. Jacobs , Paul Knappe This is my paper

Pith reviewed 2026-05-16 20:15 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C7505C05
keywords chordal graphstree-decompositionslocally finite graphscanonical decompositionsautomorphism invariancer-locally chordalHalin's theorem
0
0 comments X

The pith

A locally finite connected graph is r-locally chordal precisely when its unique canonical decomposition into r-global structure consists of cliques.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an equivalence: a locally finite connected graph has every ball of radius r/2 chordal if and only if its canonical automorphism-invariant decomposition that captures the r-scale global structure decomposes entirely into cliques. The argument rests on first establishing a canonical version of Halin's theorem, which states that chordal locally finite graphs admit tree-decompositions into cliques; the authors show these decompositions can always be chosen to remain unchanged under every automorphism of the graph. A reader would care because the result ties a purely local forbidden-cycle condition to the existence of a symmetry-preserving global splitting, offering a structural handle on infinite graphs without needing to inspect every ball separately.

Core claim

We show that a locally finite, connected graph G is r-locally chordal (that is, its r/2-balls are chordal) if and only if the unique canonical graph-decomposition H_r(G) of G displaying its r-global structure is into cliques. Our proof relies on a canonical version of Halin's characterization of chordal locally finite graphs as those that admit a tree-decomposition into cliques: We show that such tree-decompositions can be chosen to be canonical, that is, so that they are invariant under all the graph's automorphisms.

What carries the argument

The unique canonical graph-decomposition H_r(G) displaying the r-global structure of G, which is an automorphism-invariant tree-decomposition whose bags capture the large-scale connectivity.

If this is right

  • If G is r-locally chordal then every bag in H_r(G) is a clique.
  • If every bag in H_r(G) is a clique then G is r-locally chordal.
  • Chordal locally finite graphs admit a tree-decomposition into cliques that is invariant under the full automorphism group.
  • The canonical decomposition H_r(G) is unique once the r-global structure is fixed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result supplies a symmetry-preserving certificate for local chordality that could be checked on finite quotients or orbit representatives of infinite graphs.
  • It suggests analogous canonical decompositions might characterize other local forbidden-subgraph properties, such as local planarity or local bounded tree-width.
  • One could attempt to compute or approximate H_r(G) algorithmically by building successive r-balls and merging them while preserving automorphism orbits.

Load-bearing premise

A unique canonical automorphism-invariant tree-decomposition H_r(G) that displays the r-global structure exists for every locally finite connected graph.

What would settle it

A concrete locally finite connected graph whose r/2-balls are all chordal but whose unique canonical decomposition H_r(G) contains at least one bag that is not a clique, or a graph whose canonical decomposition consists only of cliques but which contains a non-chordal r/2-ball.

Figures

Figures reproduced from arXiv: 2512.18480 by Paul Knappe, Raphael W. Jacobs.

Figure 1
Figure 1. Figure 1: The graph G for Example 5.2 consists of a double-ray R = . . . e−1v−1e0v0e1v1 . . . with an apex vertex v and a further edge e = vw attached to v. Example 5.2. The graph G depicted in [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
read the original abstract

We show that a locally finite, connected graph $G$ is $r$-locally chordal (that is, its $r/2$-balls are chordal) if and only if the unique canonical graph-decomposition $\mathcal{H}_r(G)$ of $G$ displaying its $r$-global structure is into cliques. Our proof relies on a canonical version of Halin's characterization of chordal locally finite graphs as those that admit a tree-decomposition into cliques: We show that such tree-decompositions can be chosen to be canonical, that is, so that they are invariant under all the graph's automorphisms.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves an if-and-only-if characterization: a locally finite connected graph G is r-locally chordal (i.e., all r/2-balls are chordal) precisely when its unique canonical automorphism-invariant tree-decomposition H_r(G) displaying the r-global structure has all bags as cliques. The argument first establishes a canonical version of Halin's theorem guaranteeing an automorphism-invariant tree-decomposition into cliques for chordal locally finite graphs, then shows that this canonical object coincides with the r-global structure decomposition exactly under the local chordality hypothesis.

Significance. If the result holds, it supplies a canonical, symmetry-preserving tool for decomposing infinite graphs whose local balls satisfy chordality, extending Halin's classical theorem in a manner that respects automorphism groups. This invariance property is a genuine strength, as it yields a well-defined object independent of arbitrary choices and supports applications to highly symmetric graphs.

major comments (2)
  1. [Canonical version of Halin's theorem] The construction of the canonical Halin decomposition (used to define H_r(G)) must explicitly verify that the invariance under Aut(G) is achieved without invoking the axiom of choice in a way that would break canonicity; the current argument sketch leaves open whether the selection of bags is uniquely determined by the automorphism action.
  2. [Equivalence proof] In the equivalence, the direction 'H_r(G) into cliques implies r-locally chordal' requires a precise link between the bags of the r-global decomposition and the chordality of individual r/2-balls; it is unclear whether chordality of the bags directly forces chordality of the balls or whether an additional intersection property is needed.
minor comments (2)
  1. [Abstract] The abstract introduces the notation H_r(G) and 'r-global structure' without a one-sentence definition; adding a brief gloss would improve accessibility.
  2. [Introduction] A reference to Halin's original 1960s result on tree-decompositions of chordal graphs should be included in the introduction for historical context.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, the positive recommendation, and the insightful comments that help strengthen the presentation of our results on canonical decompositions. We address each major comment below and will revise the manuscript to incorporate the suggested clarifications.

read point-by-point responses

  1. Referee: [Canonical version of Halin's theorem] The construction of the canonical Halin decomposition (used to define H_r(G)) must explicitly verify that the invariance under Aut(G) is achieved without invoking the axiom of choice in a way that would break canonicity; the current argument sketch leaves open whether the selection of bags is uniquely determined by the automorphism action.

    Authors: We agree that an explicit verification is needed. The canonical Halin decomposition is constructed by taking the unique Aut(G)-invariant collection of maximal cliques (which exist and are well-defined by local finiteness) and forming the tree-decomposition whose bags are the orbits under the automorphism group action; this selection is uniquely determined by the group action and requires no appeal to the axiom of choice. We will revise the relevant section to include a dedicated paragraph spelling out this construction step by step, confirming both invariance and uniqueness without choice. revision: yes

  2. Referee: [Equivalence proof] In the equivalence, the direction 'H_r(G) into cliques implies r-locally chordal' requires a precise link between the bags of the r-global decomposition and the chordality of individual r/2-balls; it is unclear whether chordality of the bags directly forces chordality of the balls or whether an additional intersection property is needed.

    Authors: The referee correctly identifies a point that benefits from greater precision. In the proof, chordality of the bags together with the tree-decomposition properties (connected subtrees for each vertex and the Helly property for cliques) ensures that any cycle in an r/2-ball lies entirely within a single bag or a union of intersecting bags that remains chordal. We will add an auxiliary lemma making this link explicit, including the required intersection property, and insert it into the equivalence argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation establishes a canonical automorphism-invariant tree-decomposition extending Halin's theorem independently of the r-locally chordal condition, then proves the if-and-only-if equivalence by showing that this object coincides with the separately defined r-global structure decomposition precisely when the r/2-balls are chordal. The definition of H_r(G) as the unique canonical decomposition displaying r-global structure does not presuppose chordality of balls, and no equations, parameters, or self-citations reduce the central claim to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Relies on standard definitions of chordal graphs, tree-decompositions, local finiteness, and automorphism groups; no free parameters or invented entities introduced.

axioms (2)
  • standard math Halin's characterization of chordal locally finite graphs via tree-decompositions into cliques
    The paper explicitly builds its canonical version on this prior result.
  • domain assumption Existence of a unique canonical graph-decomposition displaying r-global structure
    Invoked as the object whose clique property is equivalent to r-local chordality.

pith-pipeline@v0.9.0 · 5394 in / 1075 out tokens · 38607 ms · 2026-05-16T20:15:23.110955+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

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

9 extracted references · 9 canonical work pages

  1. [1]

    [AKK25] T

    arXiv: 2512.19044. [AKK25] T. Abrishami, P. Knappe, and J. Kobler. Locally chordal graphs

    work page arXiv

  2. [2]

    An introduction to chordal graphs and clique trees

    arXiv:2501.17320. [BP93] J. R. Blair and B. Peyton. “An introduction to chordal graphs and clique trees”. In:Graph theory and sparse matrix computation(1993), pp. 1–29. [CHM22] J. Carmesin, M. Hamann, and B. Miraftab. “Canonical trees of tree-decompositions”. In: Journal of Combinatorial Theory, Series B152 (2022), pp. 1–26. [CJKK25] J. Carmesin, R. W. Ja...

    work page arXiv 1993

  3. [3]

    Entanglements

    arXiv: 2501.16170v1. [CK24] J. Carmesin and J. Kurkofka. “Entanglements”. In:Journal of Combinatorial Theory, Series B 164 (2024), pp. 17–28. [D25] R. Diestel.Graph Theory. 6th edition. Electronic edition available atwww.diestel-graph- theory.com. Springer,

    work page arXiv 2024

  4. [4]

    On rigid circuit graphs

    [D61] G. A. Dirac. “On rigid circuit graphs”. In:Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg25.1 (1961), pp. 71–76. [D88] R. Diestel. “Simplicial minors and decompositions of graphs”. In:Mathematical Proceedings of the Cambridge Philosophical Society103.3 (1988), pp. 409–426. [D91] R. Diestel. “Decomposing infinite graphs”. In:Disc...

    work page 1961

  5. [5]

    Vertex cuts

    arXiv:2207.04855. [DK15] M. J. Dunwoody and B. Krön. “Vertex cuts”. In:Journal of Graph Theory80.2 (2015), pp. 136–

    work page arXiv 2015

  6. [6]

    Trees of tangles in abstract separation systems

    [EKT21] C. Elbracht, J. L. Kneip, and M. Teegen. “Trees of tangles in abstract separation systems”. In: Journal of Combinatorial Theory, Series A180 (2021), p. 105425. [EKT22] C. Elbracht, J. L. Kneip, and M. Teegen. “Trees of tangles in infinite separation systems”. In: Mathematical Proceedings of the Cambridge Philosophical Society173.2 (2022), pp. 297–...

    work page 2021

  7. [7]

    Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen

    [H64] R. Halin. “Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen”. In: Mathematische Annalen156.3 (1964), pp. 216–225. [H89] R. Halin. Graphentheorie. De Gruyter,

    work page 1964

  8. [8]

    Clique Trees of Infinite Locally Finite Chordal Graphs

    [HL18] C. Hofer-Temmel and F. Lehner. “Clique Trees of Infinite Locally Finite Chordal Graphs”. In: The Electronic Journal of Combinatorics25.2 (2018), pp. 2–9. REFERENCES 19 [HLMR22] M. Hamann, F. Lehner, B. Miraftab, and T. Rühmann. “A Stallings type theorem for quasi- transitive graphs”. In:Journal of Combinatorial Theory, Series B157 (2022), pp. 40–69...

    work page 2018

  9. [9]

    Graph Minors I–XX

    [RS04] N. Robertson and P. D. Seymour. “Graph Minors I–XX”. In:Journal of Combinatorial Theory, Series B(1983–2004). Universität Hamburg, Department of Mathematics, Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany Email address: {raphael.jacobs, paul.knappe}@uni-hamburg.de

    work page 1983