pith. sign in

arxiv: 2212.07205 · v3 · submitted 2022-12-14 · 💻 cs.LO

Unfoldings and coverings of weighted graphs

Bruno Courcelle This is my paper

Pith reviewed 2026-05-24 10:44 UTC · model grok-4.3

classification 💻 cs.LO
keywords graph coveringsgraph unfoldingsweighted graphsuniversal coveringssurjective homomorphismsregular treescharacteristic polynomialscanonical factorization
0
0 comments X

The pith

Attaching weights to edges produces a canonical factorization of the universal covering of any finite graph that is impossible without weights.

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

The paper studies coverings of undirected graphs and unfoldings of directed graphs, both defined by surjective homomorphisms, and proves for unfoldings results analogous to Leighton and Norris theorems on coverings. It then generalizes both notions by attaching finite or infinite weights to edges. This weighted setting yields a canonical factorization of the universal covering of any finite graph, a factorization that cannot exist in the unweighted case. The same weighting also supplies finite descriptions of regular trees whose nodes have countably infinite degree and extends the classical factorization of characteristic polynomials to the weighted case.

Core claim

Generalizing coverings and unfoldings to weighted graphs produces a canonical factorization of the universal covering of any finite graph that provably does not exist without weights; infinite weights give finite descriptions of regular trees with nodes of countably infinite degree; the weighted setting also generalizes the classical factorization theorem for characteristic polynomials of graphs and their coverings.

What carries the argument

The weighted generalization of coverings and unfoldings, which attaches finite or infinite weights to edges while preserving surjective homomorphisms and enabling a unique canonical factorization.

If this is right

  • Every finite graph has a canonical factorization of its universal covering once edges carry weights.
  • Regular trees whose nodes have countably infinite degree admit finite descriptions when infinite weights are allowed.
  • The classical factorization theorem for characteristic polynomials extends directly to weighted graphs and their coverings.
  • Unfoldings satisfy statements parallel to the Leighton and Norris theorems once weights are introduced.

Where Pith is reading between the lines

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

  • The weighted approach may supply uniform finite representations for other infinite regular structures arising from graph homomorphisms.
  • Applications in distributed computing and program semantics could benefit from the finite descriptions of infinite unfoldings.
  • The method suggests examining whether other homomorphism-based constructions on graphs become canonically factorable under suitable weightings.

Load-bearing premise

The chosen weighting scheme preserves the surjective homomorphism property while enabling a unique canonical factorization that is provably impossible without weights.

What would settle it

Exhibit a finite graph together with all possible finite and infinite weight assignments on its edges such that no canonical factorization of its universal covering exists.

Figures

Figures reproduced from arXiv: 2212.07205 by Bruno Courcelle.

Figure 1
Figure 1. Figure 1: A weighted surjection, see Example 2.2(1). [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The weighted set S of Example 2.2(3). If, with the same weighted set X, we take Y consisting of y1, . . . , yn, . . . all of weight ω, then we can take S to consist of (b, y1) of weight 4, (c, y1) of weight 2 and (a, yi) and (d, yi) of weight ω for all i. □ 2.2. Graphs By a graph we mean an undirected graph, and we call digraph a directed graph, for shortness sake. A graph is defined as a triple G = (V, E,… view at source ↗
Figure 3
Figure 3. Figure 3: A digraph G and its quotient G/ ≈, cf. Example 3.12. We now consider the case where R is a regular tree. Theorem 3.14 will prove that ≈ and G/ ≈ are computable if G is finite. Theorem 3.13: (1) A rooted tree T is regular of index at most p if it is the complete unfolding of a finite, rooted and weighted digraph having p vertices. (2) Conversely, a regular tree T is the complete unfolding of a unique rooted… view at source ↗
Figure 4
Figure 4. Figure 4: None of these graphs covers any smaller graph. See Example 4.4. [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: See Remark 4.17 For an example illustrating this construction, [PITH_FULL_IMAGE:figures/full_fig_p026_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The graph H and the digraph Sym(H) of Example 5.4. Example 5.4 [PITH_FULL_IMAGE:figures/full_fig_p033_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: shows the rooted tree Unf (Sym(H)x) ↾ 3 that consists in the first three levels of Unf (Sym(H)x). Its root is denoted by x. □ [PITH_FULL_IMAGE:figures/full_fig_p033_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The rooted tree UC(H, x) ↾ 3 = P r(Unf(Sym(H)x)) ↾ 3. See Example 5.6. The following theorem is similar to Theorem 3.5. We recall that Unr forgets the root and removes the orientations of a rooted tree. Theorem 5.7: Let H be a connected and weighted graph. 1) For each x ∈ VH, the tree Unr(UC(H, x)) is a universal covering of H. 2) If µ : T → H is a universal covering, then: (C) For every covering κ : G → H… view at source ↗
Figure 9
Figure 9. Figure 9: A weighted graph H and the digraph ES(H), see Example 5.9. If R is a rooted tree, we define Sym(R) by adding to R an ”up-going” arc v → u for each arc u → v. It is nothing but Sym(Unr(R)) constructed by Definition 5.3 with all weights equal to 1 and a linear order such that x < y if x → y in R. We obtain a strongly connected rooted digraph with root rtR. See [PITH_FULL_IMAGE:figures/full_fig_p036_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The tree Unf(ES(H), x) ↾ 2, cf. Example 4.11 [PITH_FULL_IMAGE:figures/full_fig_p037_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The top part of the digraph Sym(UC(H, x)), cf. Examples 5.4 and 5.9. Proposition 5.10: Let H be a weighted connected graph and x ∈ VH. We have Unf (Sym(UC(H, x))) ≃ Unf (ES(H), x). Proof: Let γ : UC(H, x) → H be the covering homomorphism25. It is actually a homomorphism: UC(H, x) → ES(H) that is not surjective on arcs because of pruning. We extend γ into a surjective homo￾morphism γ ′ : Sym(UC(H, x)) → ES… view at source ↗
read the original abstract

Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both defined in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are infinite trees that are regular if the initial graphs are finite. Regularity means that a tree has finitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings. We prove similar statements for unfoldings. Our study of the difficult proof of Leighton's Theorem lead us to generalize coverings and similarly, unfoldings, by attaching finite or infinite weights to edges of the covered or unfolded graphs. This generalization yields a canonical factorization of the universal covering of any finite graph, that (provably) does not exist without using weights. Introducing infinite weights provides us with finite descriptions of regular trees having nodes of countably infinite degree. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

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

3 major / 2 minor

Summary. The paper studies coverings of undirected graphs and unfoldings of directed graphs, both defined via surjective homomorphisms, and proves statements analogous to those of Leighton and Norris for the unfolding case. By generalizing both notions to weighted graphs (with finite or infinite edge weights), it claims to obtain a canonical factorization of the universal covering of any finite graph that provably cannot exist in the unweighted setting; it also uses infinite weights to give finite descriptions of regular trees with countably infinite node degrees and extends a classical factorization result for characteristic polynomials to the weighted case.

Significance. If the central claims hold, the weighted generalization supplies a canonical factorization unavailable in the standard setting and extends the theory to regular trees of infinite degree, which would be of interest for applications in distributed computing and program semantics. The explicit construction of weights that simultaneously preserve surjective homomorphisms and enable uniqueness would constitute a genuine technical contribution.

major comments (3)
  1. [weighted generalization section] The section introducing the weighted generalization (following the discussion of Leighton's theorem): the claim that the factorization 'provably does not exist without using weights' is load-bearing for the main result, yet the manuscript must explicitly verify that the chosen weighting (finite or infinite) preserves the surjectivity of the homomorphisms that define coverings and unfoldings; without this verification the reduction to the unweighted case does not follow.
  2. [canonical factorization theorem] The proof of the canonical factorization theorem: the argument that the factorization is unique and canonical relies on the weighting scheme; the manuscript should supply the explicit construction of the weights and the uniqueness argument, together with a direct comparison showing why no such factorization exists for ordinary (unweighted) graphs.
  3. [characteristic polynomials section] The extension of the characteristic-polynomial factorization: the statement that the classical result generalizes to weighted graphs requires an explicit statement of the weighted characteristic polynomial and the precise factorization identity that is proved.
minor comments (2)
  1. [abstract] The abstract asserts proofs of analogous statements but does not indicate where the derivations appear; the introduction or a dedicated section should contain a clear roadmap to the proofs.
  2. [notation] Notation for finite versus infinite weights should be introduced once and used consistently; currently the distinction is mentioned only informally.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We address each major comment below and will revise the manuscript to incorporate the requested clarifications and explicit arguments.

read point-by-point responses

  1. Referee: [weighted generalization section] The section introducing the weighted generalization (following the discussion of Leighton's theorem): the claim that the factorization 'provably does not exist without using weights' is load-bearing for the main result, yet the manuscript must explicitly verify that the chosen weighting (finite or infinite) preserves the surjectivity of the homomorphisms that define coverings and unfoldings; without this verification the reduction to the unweighted case does not follow.

    Authors: We agree that an explicit verification of surjectivity preservation is necessary to support the reduction and the load-bearing claim. In the revised manuscript we will add a dedicated lemma (or subsection) proving that both finite and infinite weight assignments preserve the surjectivity of the defining homomorphisms for coverings and unfoldings. revision: yes

  2. Referee: [canonical factorization theorem] The proof of the canonical factorization theorem: the argument that the factorization is unique and canonical relies on the weighting scheme; the manuscript should supply the explicit construction of the weights and the uniqueness argument, together with a direct comparison showing why no such factorization exists for ordinary (unweighted) graphs.

    Authors: We will expand the proof of the canonical factorization theorem to include the explicit weight construction, the full uniqueness argument, and a direct comparison (via a short counter-example or impossibility argument) demonstrating that no analogous factorization exists in the unweighted setting. These additions will make the canonical character of the weighted factorization fully rigorous. revision: yes

  3. Referee: [characteristic polynomials section] The extension of the characteristic-polynomial factorization: the statement that the classical result generalizes to weighted graphs requires an explicit statement of the weighted characteristic polynomial and the precise factorization identity that is proved.

    Authors: We will insert an explicit definition of the weighted characteristic polynomial (including how weights enter the matrix or determinant) together with the precise factorization identity that is established. This will clarify the precise statement being generalized from the classical unweighted case. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is a self-contained theoretical generalization

full rationale

The paper generalizes the definitions of coverings and unfoldings via edge weights (finite or infinite) and proves that this enables a canonical factorization of the universal covering for finite graphs, which is impossible in the unweighted case. No equations, fitted parameters, or predictions appear. The central claims rest on mathematical proofs extending existing homomorphism-based definitions rather than on any self-definitional loop, fitted input renamed as prediction, or load-bearing self-citation. The weighting scheme is introduced explicitly as a generalization that preserves surjective homomorphisms while adding structure; the non-existence claim without weights is presented as a provable consequence, not presupposed. This matches the default expectation of a non-circular theoretical paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard graph-homomorphism definitions and introduces weights as a new device; no free parameters or invented entities beyond the weighting scheme are mentioned.

axioms (1)
  • standard math Standard definitions of undirected and directed graphs, surjective homomorphisms, and regularity of trees (finitely many subtrees up to isomorphism).
    Invoked throughout the abstract to define coverings, unfoldings, and the objects to which weights are attached.
invented entities (1)
  • Finite and infinite edge weights no independent evidence
    purpose: To generalize coverings and unfoldings so that a canonical factorization of the universal covering becomes possible.
    Introduced in the paper to obtain the factorization that does not exist without weights; no independent evidence outside the construction is supplied.

pith-pipeline@v0.9.0 · 5706 in / 1266 out tokens · 24306 ms · 2026-05-24T10:44:35.440579+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    On the complexity and combinatorics of covering finite complexes, Australasian J

    Abello J, Fellows MR, and Stillwell J. On the complexity and combinatorics of covering finite complexes, Australasian J. Combinatorics, 1991. 4:103–112

    work page 1991

  2. [2]

    Local and global properties in networks of processors (extended abstract)

    Angluin D. Local and global properties in networks of processors (extended abstract). Proceedings of Symposium on Theory of Computing, 1980, pp. 82–93

    work page 1980

  3. [3]

    Finite common coverings of pairs of regular graphs, J

    Angluin D, and Gardiner A. Finite common coverings of pairs of regular graphs, J. of Combinatorial Theory, Series B, 1981. 30(2):184–187. doi:10.1016/0095-8956(81)90062-9

    work page doi:10.1016/0095-8956(81)90062-9 1981

  4. [4]

    Finite transition systems, Prentice-Hall, 1994 (translated by J

    Arnold A. Finite transition systems, Prentice-Hall, 1994 (translated by J. Plaice)

    work page 1994

  5. [5]

    Uniform tree lattices, Jour

    Bass H, and Kulkarni R. Uniform tree lattices, Jour. of the American Math. Society , 1990. 3:843–902. doi:10.2307/1990905

    work page doi:10.2307/1990905 1990

  6. [6]

    Tight lower and upper bounds for the complexity of canonical colour refinement

    Berkholz C, Bonsma P, and Grohe M. Tight lower and upper bounds for the complexity of canonical colour refinement. Proceedings of ESA 2013 , Lecture Notes in Computer Science 2013. 8125 pp. 145–

    work page 2013

  7. [7]

    doi:10.1007/978-3-642-40450-4 13

    work page doi:10.1007/978-3-642-40450-4

  8. [8]

    The classification of coverings of processor networks

    Bodlaender H. The classification of coverings of processor networks. J. Parallel Distrib. Comput. 1989. 6(1):166–182. doi:10.1016/0743-7315(89)90048-8

    work page doi:10.1016/0743-7315(89)90048-8 1989

  9. [9]

    Simulation of large networks on smaller networks

    Bodlaender H, and van Leeuwen J. Simulation of large networks on smaller networks. Information and Control 1986. 71(3):143–180. doi:10.1016/S0019-9958(86)80008-0

    work page doi:10.1016/s0019-9958(86)80008-0 1986

  10. [10]

    Fibrations of graphs

    Boldi P, and Vigna S. Fibrations of graphs. Discrete Mathematics. 2002. 243 :21–66. doi:10.1016/S0012- 365X(00)00455-6

    work page doi:10.1016/s0012- 2002

  11. [11]

    Fundamental properties of infinite trees

    Courcelle B. Fundamental properties of infinite trees. Theor. Comput. Sci. 1983. 25(2):95–169. doi:10.1016/0304-3975(83)90059-2

    work page doi:10.1016/0304-3975(83)90059-2 1983

  12. [12]

    Recursive applicative program schemes, in Handbook of Theoretical Computer Science, vol

    Courcelle B. Recursive applicative program schemes, in Handbook of Theoretical Computer Science, vol. B, Elsevier, 1990, pp. 459-492

    work page 1990

  13. [13]

    The monadic second-order logic of graphs IX: Machines and their behaviours

    Courcelle B. The monadic second-order logic of graphs IX: Machines and their behaviours. Theor. Com- put. Sci. 1995. 151(1):125–162. doi:10.1016/0304-3975(95)00049-3

    work page doi:10.1016/0304-3975(95)00049-3 1995

  14. [14]

    Regular and strongly regular infinite trees, 2023, in preparation

    Courcelle B. Regular and strongly regular infinite trees, 2023, in preparation

    work page 2023

  15. [15]

    Graph structure and monadic second-order logic, a language theoretic approach, Cambridge University Press, 2012

    Courcelle B, and Engelfriet J. Graph structure and monadic second-order logic, a language theoretic approach, Cambridge University Press, 2012. doi:10.1017/CBO9780511977619

    work page doi:10.1017/cbo9780511977619 2012

  16. [16]

    Monadic second-order logic, graph coverings and unfoldings of transition systems

    Courcelle B, and Walukiewicz I. Monadic second-order logic, graph coverings and unfoldings of transition systems. Ann. Pure Appl. Logic. 1998. 92(1):35–62. doi:10.1016/S0168-0072(97)00048-1

    work page doi:10.1016/s0168-0072(97)00048-1 1998

  17. [17]

    Locally constrained graph homomorphisms - structure, complexity, and applica- tions

    Fiala J, and Kratochv ´ıl J. Locally constrained graph homomorphisms - structure, complexity, and applica- tions. Computer Science Review. 2008. 2(2):97–111. doi:10.1016/j.cosrev.2008.06.001

    work page doi:10.1016/j.cosrev.2008.06.001 2008

  18. [18]

    Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth

    Krebs A, and Verbitsky O. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. Proceedings of Logic in Computer Science , 2015, pp. 689-700. doi:10.1109/LICS.2015.69

    work page doi:10.1109/lics.2015.69 2015

  19. [19]

    Finite common coverings of graphs

    Leighton F. Finite common coverings of graphs. J. Comb. Theory, Ser. B . 1982. 33(3):231–238. doi:10.1016/0095-8956(82)90042-9

    work page doi:10.1016/0095-8956(82)90042-9 1982

  20. [20]

    A common cover of graphs and 2-cell embeddings,J

    Mohar B. A common cover of graphs and 2-cell embeddings,J. Comb. Theory, Ser. B. 1986. 40(1):94–106. doi:10.1016/0095-8956(86)90067-5. B. Courcelle / Unfoldings and Coverings 47

    work page doi:10.1016/0095-8956(86)90067-5 1986

  21. [21]

    On Leighton’s graph covering theorem, Groups, Geometry and Dynamics

    Neumann WD. On Leighton’s graph covering theorem, Groups, Geometry and Dynamics . 2011. 4:863– 872

    work page 2011

  22. [22]

    Universal covers of graphs: Isomorphism to depth n − 1 implies isomorphism to all depths, Discrete Applied Math

    Norris N. Universal covers of graphs: Isomorphism to depth n − 1 implies isomorphism to all depths, Discrete Applied Math. 1995. 56(1):61–74. doi:10.1016/0166-218X(93)E0133-J

    work page doi:10.1016/0166-218x(93)e0133-j 1995

  23. [23]

    Einf¨uhrung in die kombinatorische Topologie, F

    Reidemeister K. Einf¨uhrung in die kombinatorische Topologie, F. Vieweg and Sohn, 1932 (and Springer, 1951)

    work page 1932

  24. [24]

    Fractional Graph Theory, J.Wiley, 2008, https://www.ams.jhu.edu/ ers/wp-content/uploads/2015/12/fgt.pdf

    Scheinerman E, and Ullman D. Fractional Graph Theory, J.Wiley, 2008, https://www.ams.jhu.edu/ ers/wp-content/uploads/2015/12/fgt.pdf

    work page 2008

  25. [25]

    Some topological graph theory for topologists: A sampler of covering space construction, in Topology and Combinatorial Group Theory, P

    Tucker T. Some topological graph theory for topologists: A sampler of covering space construction, in Topology and Combinatorial Group Theory, P. Latiolaids ed., Lec. Notes Maths . Springer 1990. 1440:192–207

    work page 1990

  26. [26]

    Revisiting Leighton’s theorem with the Haar measure, Mathematical Proceedings of the Cambridge Philosophical Society , Cambridge University Press

    Woodhouse J. Revisiting Leighton’s theorem with the Haar measure, Mathematical Proceedings of the Cambridge Philosophical Society , Cambridge University Press . January 2020, pp. 1–9. doi:10.1017/S0305004119000550

    work page doi:10.1017/s0305004119000550 2020