pith. sign in

arxiv: 2603.02563 · v2 · submitted 2026-03-03 · 🧮 math.ST · math.PR· stat.TH

Graph Disjointness with Applications to Reversible Markov Chains

Yang Xiang , Kevin McGoff , Andrew B. Nobel This is my paper

Pith reviewed 2026-05-15 17:22 UTC · model grok-4.3

classification 🧮 math.ST math.PRstat.TH
keywords graph disjointnessreversible Markov chainsgraph joiningsspectral overlaptree graphsrandom walk couplingsMarkov chain rigidity
0
0 comments X

The pith

Two graphs without self-loops are strongly disjoint exactly when they are weakly disjoint and one of them is a tree.

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

The paper shows that disjointness between graphs can be read off from their vertex and edge sets alone, using the known link between weighted graphs and reversible Markov chains. Weak disjointness occurs precisely when the transition matrices of the two chains have no spectral overlap beyond the stationary eigenvalue. Strong disjointness then requires the additional condition that exactly one graph is a tree. This classification gives a concrete criterion for when the only reversible coupling of two chains is the product coupling.

Core claim

Two graphs G and H without self-loops are strongly disjoint if and only if they are weakly disjoint and exactly one of them is a tree. Weak disjointness is equivalent to the absence of nontrivial spectral overlap between the Markov transition matrices. Both forms of disjointness are determined solely by the underlying unweighted graphs.

What carries the argument

Graph joinings, which are graphs on the product of the vertex sets whose random walks realize couplings of the original chains; strong disjointness means the only such joining is the tensor product.

If this is right

  • Weak disjointness of graphs translates directly into rigidity of reversible couplings of the associated Markov chains.
  • The tree condition distinguishes cases where spectral non-overlap alone forces the product coupling.
  • Edge weights can be varied arbitrarily without changing whether two graphs are strongly or weakly disjoint.
  • Graph factors and joinings become tools for classifying when Markov chain couplings are forced to be independent.

Where Pith is reading between the lines

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

  • The characterization may let researchers test coupling rigidity by computing eigenvalues and checking for trees rather than searching over all possible couplings.
  • The result suggests that most pairs of graphs admit non-product reversible couplings unless spectral separation or tree structure intervenes.
  • Extending the spectral criterion to infinite graphs or directed graphs would require new joining theory but could follow the same outline.

Load-bearing premise

The standard bijection between weighted undirected graphs and reversible Markov chains via vertex random walks holds, and the graphs are finite and loop-free.

What would settle it

Exhibit two non-tree graphs whose transition matrices have no spectral overlap yet admit a joining whose degree function differs from the tensor product, or two graphs with spectral overlap that admit no such non-tensor joining.

Figures

Figures reproduced from arXiv: 2603.02563 by Andrew B. Nobel, Kevin McGoff, Yang Xiang.

Figure 1
Figure 1. Figure 1: (A) and (B) Two distinct graph joinings of the same pair of uni￾formly weighted graphs (with self-loops); (C) The only graph joining between this pair of graphs is the product joining; (D) An example of a weighted joining between two graphs with self-loops. and corresponding degree function r(u, v) = p(u)1(f(u) = v). Indeed, to check that γ is a graph joining, we note that the first transition coupling con… view at source ↗
Figure 2
Figure 2. Figure 2: A graph joining of C3 and C4 that is not the tensor product C3⊗C4. Proposition 3.7. Let m, n ≥ 3. The cycles Cm and Cn are never strongly disjoint. Moreover, Cm and Cn are weakly disjoint if and only if gcd(m, n) = 1. In particular, there exists a pair of graphs that is weakly disjoint but not strongly disjoint [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
read the original abstract

The correspondence between weighted undirected graphs and reversible Markov chains via vertex random walks is simple and well known. Leveraging this correspondence and ideas from the theory of dynamical systems, we study the structural discordance of graphs and Markov chains by means of graph joinings. Informally, a joining of graphs $G$ and $H$ is a graph on the product of their vertex sets giving rise to a coupling of their random walks. Graphs $G$ and $H$ are strongly disjoint if their only joining is the tensor product, and they are weakly disjoint if the degree function of every joining is equal to the degree function of the tensor product. We establish close connections between graph joinings, disjointness, and graph factors. Our first principal result characterizes weak disjointness of graphs in terms of the spectral overlap of their Markov transition matrices. The second establishes that two graphs without self loops are strongly disjoint if and only if they are weakly disjoint and exactly one of the graphs is a tree. The third shows that the strong or weak disjointness of graphs is essentially determined by their vertex and edge sets, without regard to edge weights. Translating these results into the language of Markov chains yields new insights into the rigidity and structure of reversible couplings of reversible Markov chains.

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 / 3 minor

Summary. The paper leverages the standard bijection between positive edge weights on finite undirected graphs without self-loops and reversible Markov chains via vertex random walks. It defines a joining of graphs G and H as a graph on the product vertex set that induces a coupling of the associated random walks. Strong disjointness means the only joining is the tensor product; weak disjointness means every joining has the same degree function as the tensor product. The three principal results are: (i) weak disjointness is equivalent to zero spectral overlap between the Markov transition matrices; (ii) for graphs without self-loops, strong disjointness holds if and only if the graphs are weakly disjoint and exactly one is a tree; (iii) both notions of disjointness depend only on the vertex and edge sets, independent of the specific positive edge weights. These are translated back to statements about the rigidity of reversible couplings of reversible Markov chains.

Significance. If the characterizations hold, the work supplies a clean structural criterion for when two reversible Markov chains admit only the independent coupling (up to the tree condition), expressed in terms of spectral overlap and graph-theoretic properties. The independence from edge weights is a notable strength, as is the explicit link to joinings from dynamical systems. The results are parameter-free once the vertex/edge sets are fixed and rest on a well-known correspondence, which strengthens their applicability to questions of coupling rigidity.

major comments (2)
  1. [§4, Theorem 3.2] §4, Theorem 3.2 (strong-disjointness characterization): the 'only if' direction invokes that the graphs are finite and without self-loops to rule out non-tensor joinings; the manuscript should explicitly state whether the finiteness hypothesis can be relaxed to locally finite graphs or whether a counter-example exists in the infinite case.
  2. [§3.1, Definition 2.4] §3.1, Definition 2.4 and Proposition 3.1: the spectral-overlap characterization of weak disjointness is stated for the normalized Laplacian or the transition matrix; the proof sketch should clarify whether the overlap is measured in the L2 inner product with respect to the stationary measure or the counting measure, as this affects the precise statement of the equivalence.
minor comments (3)
  1. [Abstract, §1] The abstract and introduction use 'tensor product' without a forward reference to its definition in §2; add an explicit cross-reference.
  2. [§2, §3] Notation for the degree function of a joining (e.g., d_{G⊗H}) is introduced in §2 but used without reminder in the statements of Theorems 3.1 and 3.2; a short notational table or consistent reminder would improve readability.
  3. [§5] The translation to Markov-chain language in §5 would benefit from one concrete numerical example (two small graphs, their transition matrices, and the resulting coupling) to illustrate the spectral-overlap condition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and the positive recommendation for minor revision. We address each of the major comments below and have incorporated the suggested clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [§4, Theorem 3.2] §4, Theorem 3.2 (strong-disjointness characterization): the 'only if' direction invokes that the graphs are finite and without self-loops to rule out non-tensor joinings; the manuscript should explicitly state whether the finiteness hypothesis can be relaxed to locally finite graphs or whether a counter-example exists in the infinite case.

    Authors: We thank the referee for this observation. The proof indeed relies on finiteness to exclude certain pathological joinings in the infinite setting. In the revised version, we have added an explicit statement in the discussion following Theorem 3.2 noting that the characterization is established under the assumption of finite graphs, and that the question of extension to locally finite graphs remains open, with no counterexamples currently known. This addresses the request for clarification without altering the main results. revision: partial

  2. Referee: [§3.1, Definition 2.4] §3.1, Definition 2.4 and Proposition 3.1: the spectral-overlap characterization of weak disjointness is stated for the normalized Laplacian or the transition matrix; the proof sketch should clarify whether the overlap is measured in the L2 inner product with respect to the stationary measure or the counting measure, as this affects the precise statement of the equivalence.

    Authors: We appreciate this request for precision. The spectral overlap is defined using the L² inner product with respect to the stationary probability measure (corresponding to the normalized Laplacian). We have revised the proof sketch in Section 3.1 to explicitly specify this, ensuring the equivalence is stated clearly with respect to the appropriate measure. This does not change the mathematical content but improves clarity. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's derivations of weak and strong disjointness characterizations proceed directly from the standard bijection between finite weighted undirected graphs without self-loops and reversible Markov chains (via vertex random walks) together with the definition of graph joinings. The first principal result equates weak disjointness to spectral overlap of transition matrices; the second equates strong disjointness to weak disjointness plus exactly one graph being a tree; the third shows independence from specific edge weights. All three follow from the joining definition and standard spectral graph theory without any fitted parameters renamed as predictions, self-citation load-bearing steps, or ansatzes smuggled via prior work by the same authors. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 3 invented entities

The paper relies on the standard correspondence between graphs and reversible Markov chains and introduces new definitions; no free parameters or invented physical entities are present.

axioms (1)
  • domain assumption Weighted undirected graphs correspond to reversible Markov chains via vertex random walks
    Described as simple and well known in the abstract.
invented entities (3)
  • graph joining no independent evidence
    purpose: Graph on the product vertex set that induces a coupling of the two random walks
    Newly introduced definition central to the disjointness notions.
  • strong disjointness no independent evidence
    purpose: Only joining is the tensor product
    Newly introduced property.
  • weak disjointness no independent evidence
    purpose: Every joining has the same degree function as the tensor product
    Newly introduced property.

pith-pipeline@v0.9.0 · 5523 in / 1367 out tokens · 86615 ms · 2026-05-15T17:22:06.790107+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

46 extracted references · 46 canonical work pages · 1 internal anchor

  1. [1]

    Lower bounds for covering times for reversible Markov chains and random walks on graphs.Journal of Theoretical Probability, 2(1):91–100, 1989

    David J Aldous. Lower bounds for covering times for reversible Markov chains and random walks on graphs.Journal of Theoretical Probability, 2(1):91–100, 1989

    work page 1989

  2. [2]

    Lumpability and marginalisability for continuous-time Markov chains.Journal of Applied Probability, 30(3):518–528, 1993

    Frank Ball and Geoffrey F Yeo. Lumpability and marginalisability for continuous-time Markov chains.Journal of Applied Probability, 30(3):518–528, 1993

    work page 1993

  3. [3]

    An eigenvector condition for Markov chain lumpa- bility.Operations Research, 25(6):1028–1031, 1977

    Donald R Barr and Marlin U Thomas. An eigenvector condition for Markov chain lumpa- bility.Operations Research, 25(6):1028–1031, 1977

    work page 1977

  4. [4]

    Algorithm 432 [c2]: Solution of the matrix equation AX+ XB= C [f4].Communications of the ACM, 15(9):820–826, 1972

    Richard H Bartels and George W Stewart. Algorithm 432 [c2]: Solution of the matrix equation AX+ XB= C [f4].Communications of the ACM, 15(9):820–826, 1972

    work page 1972

  5. [5]

    How and why to solve the operator equation AX- XB= Y.Bulletin of the London Mathematical Society, 29(1):1–21, 1997

    Rajendra Bhatia and Peter Rosenthal. How and why to solve the operator equation AX- XB= Y.Bulletin of the London Mathematical Society, 29(1):1–21, 1997

    work page 1997

  6. [6]

    Estimating convergence of Markov chains with l-lag couplings.Advances in neural information processing systems, 32, 2019

    Niloy Biswas, Pierre E Jacob, and Paul Vanetti. Estimating convergence of Markov chains with l-lag couplings.Advances in neural information processing systems, 32, 2019

    work page 2019

  7. [7]

    Symmetry analysis of re- versible Markov chains.Internet Mathematics, 2(1):31–71, 2005

    Stephen Boyd, Persi Diaconis, Pablo Parrilo, and Lin Xiao. Symmetry analysis of re- versible Markov chains.Internet Mathematics, 2(1):31–71, 2005

    work page 2005

  8. [8]

    Fastest mixing Markov chain on a graph

    Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing Markov chain on a graph. SIAM review, 46(4):667–689, 2004. 53

    work page 2004

  9. [9]

    A Markovian function of a Markov chain.The Annals of Mathematical Statistics, 29(4):1112–1122, 1958

    Cletus J Burke and Murray Rosenblatt. A Markovian function of a Markov chain.The Annals of Mathematical Statistics, 29(4):1112–1122, 1958

    work page 1958

  10. [10]

    American Mathematical Soc., 1997

    Fan RK Chung.Spectral graph theory, volume 92. American Mathematical Soc., 1997

    work page 1997

  11. [11]

    An introduction to joinings in ergodic theory

    Thierry De La Rue. An introduction to joinings in ergodic theory.arXiv preprint math/0507429, 2005

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  12. [12]

    Joinings in ergodic theory

    Thierry De La Rue. Joinings in ergodic theory. InErgodic Theory, pages 149–168. Springer, 2023

    work page 2023

  13. [13]

    The cutoff phenomenon in finite Markov chains.Proceedings of the National Academy of Sciences, 93(4):1659–1664, 1996

    Persi Diaconis. The cutoff phenomenon in finite Markov chains.Proceedings of the National Academy of Sciences, 93(4):1659–1664, 1996

    work page 1996

  14. [14]

    Analysis of a nonreversible Markov chain sampler.Annals of Applied Probability, pages 726–752, 2000

    Persi Diaconis, Susan Holmes, and Radford M Neal. Analysis of a nonreversible Markov chain sampler.Annals of Applied Probability, pages 726–752, 2000

    work page 2000

  15. [15]

    On a Markov construction of couplings.arXiv preprint arXiv:2305.02580, 2023

    Persi Diaconis and Laurent Miclo. On a Markov construction of couplings.arXiv preprint arXiv:2305.02580, 2023

    work page arXiv 2023

  16. [16]

    Geometric bounds for eigenvalues of Markov chains

    Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of Markov chains. The annals of applied probability, pages 36–61, 1991

    work page 1991

  17. [17]

    Springer Nature, 2025

    Reinhard Diestel.Graph theory. Springer Nature, 2025

    work page 2025

  18. [18]

    On cycles in the coprime graph of integers.the electronic journal of combinatorics, pages R8–R8, 1997

    Paul Erd˝ os and Gabor N Sarkozy. On cycles in the coprime graph of integers.the electronic journal of combinatorics, pages R8–R8, 1997

    work page 1997

  19. [19]

    Lumping complex networks.Lectures and Gallery of Madeira Math Encounters XXXV, 2008

    R Filliger and MO Hongler. Lumping complex networks.Lectures and Gallery of Madeira Math Encounters XXXV, 2008

    work page 2008

  20. [20]

    Disjointness in ergodic theory, minimal sets, and a problem in dio- phantine approximation.Mathematical systems theory, 1(1):1–49, 1967

    Harry Furstenberg. Disjointness in ergodic theory, minimal sets, and a problem in dio- phantine approximation.Mathematical systems theory, 1(1):1–49, 1967

    work page 1967

  21. [21]

    Minimal transformations with no common factor need not be disjoint.Israel Journal of Mathematics, 45:1–8, 1983

    Shmuel Glasner and Benjamin Weiss. Minimal transformations with no common factor need not be disjoint.Israel Journal of Mathematics, 45:1–8, 1983

    work page 1983

  22. [22]

    A generalization of Ornstein’s d distance with applications to information theory.The Annals of Probability, pages 315–328, 1975

    Robert M Gray, David L Neuhoff, and Paul C Shields. A generalization of Ornstein’s d distance with applications to information theory.The Annals of Probability, pages 315–328, 1975

    work page 1975

  23. [23]

    Opti- mal graph joining with applications to isomorphism detection and identification.arXiv preprint arXiv:2511.14862, 2025

    Phuong N Ho` ang, Kevin McGoff, Andrew B Nobel, Yang Xiang, and Bongsoo Yi. Opti- mal graph joining with applications to isomorphism detection and identification.arXiv preprint arXiv:2511.14862, 2025

    work page arXiv 2025

  24. [24]

    Coupling and mixing times in a Markov chain.Linear algebra and its applications, 430(10):2607–2621, 2009

    Jeffrey J Hunter. Coupling and mixing times in a Markov chain.Linear algebra and its applications, 430(10):2607–2621, 2009

    work page 2009

  25. [25]

    Bounds on thel 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality.Transactions of the American mathematical society, 309(2):557–580, 1988

    Gregory F Lawler and Alan D Sokal. Bounds on thel 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality.Transactions of the American mathematical society, 309(2):557–580, 1988

    work page 1988

  26. [26]

    American Mathematical Soc., 2017

    David A Levin and Yuval Peres.Markov chains and mixing times, volume 107. American Mathematical Soc., 2017

    work page 2017

  27. [27]

    FGOT: Graph distances based on filters and optimal transport

    Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. FGOT: Graph distances based on filters and optimal transport. InProceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7710–7718, 2022

    work page 2022

  28. [28]

    B. S. Mityagin. The zero set of a real analytic function.Mathematical Notes, 107(3- 4):529–530, 2020. 54

    work page 2020

  29. [29]

    Mathematical aspects of mixing times in Markov chains.Foundations and Trends®in Theoretical Computer Science, 1(3):237–354, 2006

    Ravi Montenegro, Prasad Tetali, et al. Mathematical aspects of mixing times in Markov chains.Foundations and Trends®in Theoretical Computer Science, 1(3):237–354, 2006

    work page 2006

  30. [30]

    Optimal transport for stationary Markov chains via policy iteration.Journal of Machine Learning Research, 23(45):1–52, 2022

    Kevin O’Connor, Kevin McGoff, and Andrew B Nobel. Optimal transport for stationary Markov chains via policy iteration.Journal of Machine Learning Research, 23(45):1–52, 2022

    work page 2022

  31. [31]

    Bernoulli shifts with the same entropy are isomorphic.Advances in Mathematics, 4(3):337–352, 1970

    Donald Ornstein. Bernoulli shifts with the same entropy are isomorphic.Advances in Mathematics, 4(3):337–352, 1970

    work page 1970

  32. [32]

    Markov chain Monte Carlo and irreversibility.Reports on Mathematical Physics, 77(3):267–292, 2016

    Michela Ottobre. Markov chain Monte Carlo and irreversibility.Reports on Mathematical Physics, 77(3):267–292, 2016

    work page 2016

  33. [33]

    Got: an optimal transport framework for graph comparison.Advances in Neural Infor- mation Processing Systems, 32, 2019

    Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, and Pascal Frossard. Got: an optimal transport framework for graph comparison.Advances in Neural Infor- mation Processing Systems, 32, 2019

    work page 2019

  34. [34]

    Graph factors and factorization: 1985–2003: a survey.Discrete Mathematics, 307(7-8):791–821, 2007

    Michael D Plummer. Graph factors and factorization: 1985–2003: a survey.Discrete Mathematics, 307(7-8):791–821, 2007

    work page 1985

  35. [35]

    Exact sampling with coupled Markov chains and applications to statistical mechanics.Random Structures & Algorithms, 9(1-2):223– 252, 1996

    James Gary Propp and David Bruce Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics.Random Structures & Algorithms, 9(1-2):223– 252, 1996

    work page 1996

  36. [36]

    Springer, 1999

    Christian P Robert, George Casella, and George Casella.Monte Carlo statistical methods, volume 2. Springer, 1999

    work page 1999

  37. [37]

    Some results on symmetric circulant matrices and on symmetric centrosymmetric matrices.Linear algebra and its applications, 392:211–233, 2004

    Oscar Rojo and H´ ector Rojo. Some results on symmetric circulant matrices and on symmetric centrosymmetric matrices.Linear algebra and its applications, 392:211–233, 2004

    work page 2004

  38. [38]

    New York: Springer, 2001

    Gordon F Royle and Chris Godsil.Algebraic graph theory, volume 207. New York: Springer, 2001

    work page 2001

  39. [39]

    Markov chains for exploring posterior distributions.the Annals of Statis- tics, pages 1701–1728, 1994

    Luke Tierney. Markov chains for exploring posterior distributions.the Annals of Statis- tics, pages 1701–1728, 1994

    work page 1994

  40. [40]

    A note on Metropolis-Hastings kernels for general state spaces.Annals of applied probability, pages 1–9, 1998

    Luke Tierney. A note on Metropolis-Hastings kernels for general state spaces.Annals of applied probability, pages 1–9, 1998

    work page 1998

  41. [41]

    The factors of graphs.Canadian Journal of Mathematics, 4:314– 328, 1952

    William Thomas Tutte. The factors of graphs.Canadian Journal of Mathematics, 4:314– 328, 1952

    work page 1952

  42. [42]

    Fused Gromov-Wasserstein distance for structured objects.Algorithms, 13(9):212, 2020

    Titouan Vayer, Laetitia Chapel, R´ emi Flamary, Romain Tavenard, and Nicolas Courty. Fused Gromov-Wasserstein distance for structured objects.Algorithms, 13(9):212, 2020

    work page 2020

  43. [43]

    Subgraph pooling: Tack- ling negative transfer on graphs.arXiv preprint arXiv:2402.08907, 2024

    Zehong Wang, Zheyuan Zhang, Chuxu Zhang, and Yanfang Ye. Subgraph pooling: Tack- ling negative transfer on graphs.arXiv preprint arXiv:2402.08907, 2024

    work page arXiv 2024

  44. [44]

    A survey of transfer learning

    Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1):9, 2016

    work page 2016

  45. [45]

    Prentice hall Upper Saddle River, 2001

    Douglas Brent West et al.Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001

    work page 2001

  46. [46]

    J Jw #  . If rank(J) = rank(

    Bongsoo Yi, Kevin O’Connor, Kevin McGoff, and Andrew B Nobel. Alignment and comparison of directed networks via transition couplings of random walks.Journal of the Royal Statistical Society Series B: Statistical Methodology, 87(1):186–210, 2025. 55 AppendixA.Additional Proofs A.1.Proposition 2.5. Proposition 2.5.LetG= (U, α)andH= (V, β)be graphs with degr...

    work page 2025