pith. sign in

arxiv: 2402.09568 · v2 · submitted 2024-02-14 · 💻 cs.DM · math.AC· math.CO

Irreducible Markov Chains on spaces of graphs with fixed degree-color sequences

F\'elix Almendra-Hern\'andez , Jes\'us A. De Loera , Sonja Petrovi\'c This is my paper

Pith reviewed 2026-05-24 03:58 UTC · model grok-4.3

classification 💻 cs.DM math.ACmath.CO
keywords colored graphsdegree sequencesMarkov chainsgraph samplingcolor-preserving switchesblock modelshypersimplexirreducible chains
0
0 comments X

The pith

Color-preserving switches connect the space of graphs with fixed degree-color sequences.

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

The paper proves that any two graphs sharing both a fixed degree sequence and a fixed statistic derived from a vertex coloring can be transformed into each other by sequences of color-preserving simple switches. This connectivity result lets researchers define an irreducible Markov chain on the space. The chain is needed to sample from the uniform distribution and to test whether observed block-partitioned network data fit a proposed statistical model. The same moves also produce a regular triangulation of a polytope that generalizes the second hypersimplex, extending algebraic facts known since the 1990s. For simple graphs the 1-norm of the shortest connecting sequence grows with the number of colors, unlike the monochromatic case.

Core claim

We prove that the set of graphs with a fixed degree sequence and a fixed vertex-color statistic is connected under color-preserving simple switches. These moves preserve both the degree sequence and the color statistic, and they serve as the generators of an irreducible Markov chain on the space. The construction further yields a regular triangulation of a generalization of the second hypersimplex.

What carries the argument

Color-preserving simple switches that exchange edges while respecting vertex colors and leaving the fixed degree and color statistics unchanged.

If this is right

  • The Markov chain generated by the color-preserving switches is irreducible on the space of graphs with the given statistics.
  • The chain supplies a practical method for sampling and for testing model fit on block-partitioned network data.
  • The same moves produce a regular triangulation of the generalized second hypersimplex.
  • In the simple-graph setting the 1-norm of moves needed to connect any pair grows with the number of colors.

Where Pith is reading between the lines

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

  • Similar connectivity arguments may apply when other combinatorial invariants are fixed in addition to degrees.
  • The colored-switch framework could be implemented to study mixing times on networks with explicit community structure.
  • The observed growth in move size with colors suggests that mixing-time bounds will need color-dependent analysis.
  • The triangulation result may link to other questions in algebraic combinatorics involving colored polytopes.

Load-bearing premise

An additional statistic arising from the vertex coloring can be fixed independently of the degree sequence and remains invariant under the color-preserving switches.

What would settle it

Two graphs that share the same degree sequence and the same color statistic but cannot be joined by any sequence of color-preserving switches would show the claimed connectivity fails.

read the original abstract

We study a colored generalization of the famous simple-switch Markov chain for sampling the set of graphs with a fixed degree sequence. Here we consider the space of graphs with colored vertices, in which we fix the degree sequence and another statistic arising from the vertex coloring, and prove that the set can be connected with simple color-preserving switches or moves. These moves form a basis for defining an irreducible Markov chain necessary for testing statistical model fit to block-partitioned network data. Our methods further generalize well-known algebraic results from the 1990s: namely, that the corresponding moves can be used to construct a regular triangulation for a generalization of the second hypersimplex. On the other hand, in contrast to the monochromatic case, we show that for \emph{simple} graphs, the 1-norm of the moves necessary to connect the space increases with the number of colors.

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

1 major / 0 minor

Summary. The manuscript develops a colored generalization of the simple-switch Markov chain on graphs with fixed degree sequences. It defines the state space by additionally fixing a statistic derived from the vertex coloring, proves that this space is connected under color-preserving switches, and shows that these moves yield an irreducible Markov chain suitable for goodness-of-fit testing on block-partitioned networks. The work also extends 1990s algebraic results by constructing a regular triangulation of a generalized second hypersimplex, while establishing that the 1-norm of the required moves grows with the number of colors in the simple-graph case.

Significance. If the connectivity and invariance arguments hold, the result supplies a combinatorial foundation for MCMC sampling on spaces of graphs with both degree and block-structure constraints, directly supporting statistical inference for networks with vertex types. The algebraic extension to hypersimplex triangulations is a clear contribution that generalizes prior monochromatic work.

major comments (1)
  1. [Abstract] Abstract: the central claim requires that a color-derived statistic exists which can be fixed independently of the degree sequence and is exactly preserved by the color-preserving switches. The abstract asserts this invariance but does not exhibit the explicit construction of the statistic or the verification that it remains unchanged under all allowed moves when multiple colors interact with the simple-graph condition; this step is load-bearing for both the definition of the state space and the irreducibility argument.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We address the single major comment below and will revise the manuscript to improve clarity in the abstract.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim requires that a color-derived statistic exists which can be fixed independently of the degree sequence and is exactly preserved by the color-preserving switches. The abstract asserts this invariance but does not exhibit the explicit construction of the statistic or the verification that it remains unchanged under all allowed moves when multiple colors interact with the simple-graph condition; this step is load-bearing for both the definition of the state space and the irreducibility argument.

    Authors: We agree that the abstract would benefit from greater explicitness on this point. The manuscript defines the color-derived statistic in Section 2 as the sequence pairing each vertex's prescribed color with its degree (i.e., the degree-color sequence), which is fixed independently of the ordinary degree sequence. Color-preserving switches are defined to act only on pairs of vertices whose colors are compatible with the fixed sequence; the proof that these moves preserve the statistic appears in the invariance lemma preceding the connectivity theorem. We will revise the abstract to include a concise description of the statistic and a one-sentence statement of its invariance, thereby making the load-bearing step visible without altering the paper's technical content. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial proof; no reductions to inputs by construction

full rationale

The paper establishes connectivity of the space of colored graphs with fixed degree sequence plus an additional color-derived statistic via explicit color-preserving switches. This is presented as a combinatorial generalization of 1990s algebraic results on hypersimplices, with the moves defined to preserve the fixed statistics by construction. The proof itself does not reduce any claimed result to a fitted parameter, self-citation chain, or definitional tautology; the invariance under switches follows from the move definition, while connectivity is shown independently. No load-bearing self-citations or ansatzes are invoked in the abstract or described methods. This is a standard non-circular combinatorial argument.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard graph-theoretic definitions and algebraic results from the 1990s; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of graphs, degree sequences, switch operations, and hypersimplices from combinatorial literature.
    The colored generalization and triangulation claim presuppose these background notions.

pith-pipeline@v0.9.0 · 5696 in / 1179 out tokens · 45143 ms · 2026-05-24T03:58:04.000849+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

34 extracted references · 34 canonical work pages

  1. [1]

    Abdullah, C

    M. Abdullah, C. Cooper, and A. Frieze. Cover time of a random graph with given degree sequence. In 21st I nternational M eeting on P robabilistic, C ombinatorial, and A symptotic M ethods in the A nalysis of A lgorithms ( A of A '10) , volume AM of Discrete Math. Theor. Comput. Sci. Proc., pages 1--19. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2010

    work page 2010

  2. [2]

    Almendra-Hern\'andez, J

    F. Almendra-Hern\'andez, J. A. De Loera , and S. Petrovi\'c. Markov bases: a 25 year update. Journal of the A merican S tatistical A ssociation, to appear. Preprint arXiv:2306.06270 , 2023

    work page arXiv 2023

  3. [3]

    S. Aoki, H. Hara, and A. Takemura. Markov Bases in Algebraic Statistics. Springer Series in Statistics. Springer New York, 2012

    work page 2012

  4. [4]

    B\' e rczi, Z

    K. B\' e rczi, Z. Kir\' a ly, C. Liu, and I. Mikl\' o s. Packing tree degree sequences. Informatica (Ljubl.), 43 0 (1): 0 11--17, 2019

    work page 2019

  5. [5]

    Chatterjee, P

    S. Chatterjee, P. Diaconis, and A. Sly. Random graphs with a given degree sequence. Ann. Appl. Probab., 21 0 (4): 0 1400--1435, 2011

    work page 2011

  6. [6]

    Cloteaux

    B. Cloteaux. Fast sequential creation of random realizations of degree sequences. Internet Math., 12 0 (3): 0 205--219, 2016

    work page 2016

  7. [7]

    Cooper and A

    C. Cooper and A. Frieze. A general model of web graphs. Random Structures & Algorithms, 22 0 (3): 0 311--335, 2003

    work page 2003

  8. [8]

    D. A. Cox, J. B. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Springer, 4th edition, 2015

    work page 2015

  9. [9]

    J. A. De Loera, B. Sturmfels, and R. R. Thomas. Gr\" o bner bases and triangulations of the second hypersimplex. Combinatorica, 15 0 (3): 0 409--424, 1995

    work page 1995

  10. [10]

    J. A. De Loera, J. Rambau, and F. Santos. Triangulations: Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Springer Berlin Heidelberg, 2010

    work page 2010

  11. [11]

    Deeds, D

    K. Deeds, D. Suciu, M. Balazinska, and W. Cai. Degree sequence bound for join cardinality estimation. In 26th I nternational C onference on D atabase T heory , volume 255 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 8, 18. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023

    work page 2023

  12. [12]

    A. Deza, A. Levin, S. M. Meesum, and S. Onn. Optimization over degree sequences. SIAM J. Discrete Math., 32 0 (3): 0 2067--2079, 2018

    work page 2067

  13. [13]

    Diaconis and B

    P. Diaconis and B. Sturmfels. Algebraic algorithms for sampling from conditional distributions. Annals of Statistics, 26 0 (1): 0 363--397, 1998

    work page 1998

  14. [14]

    Erdős and T

    P. Erdős and T. Gallai. Gráfok előírt fokszámú pontokkal. Matematikai Lapok, 11: 0 264–274, 1960

    work page 1960

  15. [15]

    P. L. Erdős, C. Greenhill, T. R. Mezei, I. Miklós, D. Soltész, and L. Soukup. The mixing time of switch markov chains: A unified approach. European Journal of Combinatorics, 99: 0 103421, 2022

    work page 2022

  16. [16]

    S. E. Fienberg, M. M. Meyer, and S. S. Wasserman. Statistical analysis of multiple sociometric relations. Journal of the American Statistical Association, 80 0 (389): 0 51--67, 1985

    work page 1985

  17. [17]

    S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. i. Journal of the Society for Industrial and Applied Mathematics, 10: 0 496--506, 1962

    work page 1962

  18. [18]

    V. Havel. A remark on the existence of finite graphs. Časopis pro pěstování matematiky, 80: 0 477--480, 1955

    work page 1955

  19. [19]

    Hemmecke and P

    R. Hemmecke and P. N. Malkin. Computing generating sets of lattice ideals and markov bases of lattices. Journal of Symbolic Computation, 44 0 (10): 0 1463--1476, 2009

    work page 2009

  20. [20]

    P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5 0 (2): 0 109--137, 1983

    work page 1983

  21. [21]

    Kannan, P

    R. Kannan, P. Tetali, and S. S. Vempala. Simple M arkov-chain algorithms for generating bipartite graphs and tournaments. Random Structures & Algorithms, 14: 0 293--308, 1997

    work page 1997

  22. [22]

    Karwa, D

    V. Karwa, D. Pati, S. Petrovi \'c , L. Solus, N. Alexeev, M. Rai c , D. Wilburne, R. Williams, and B. Yan. Monte C arlo goodness-of-fit tests for degree corrected and related stochastic blockmodels. J ournal of the R oyal S tatistical S ociety, Series B , 2023

    work page 2023

  23. [23]

    S. Onn. Degree sequence optimization in bounded treewidth. Optimization Letters, 17: 0 1127--1132, 2023

    work page 2023

  24. [24]

    Palmer and J

    C. Palmer and J. Steffan. Generating network topologies that obey power laws. In Globecom '00 - IEEE. Global Telecommunications Conference. Conference Record (Cat. No.00CH37137), volume 1, pages 434--438 vol.1, 2000

    work page 2000

  25. [25]

    U. N. Peled and M. K. Srinivasan. The polytope of degree sequences. Linear Algebra Appl., 114/115: 0 349--377, 1989

    work page 1989

  26. [26]

    Petrovi \' c

    S. Petrovi \' c . What is... a M arkov B asis? Notices of the American Mathematical Society, 66 0 (07): 0 1, Aug. 2019. doi:10.1090/noti1904

    work page doi:10.1090/noti1904 2019

  27. [27]

    Petrovi\'c and D

    S. Petrovi\'c and D. Stasi. Toric algebra of hypergraphs. Journal of Algebraic Combinatorics, 39 0 (1): 0 187--208, 2014

    work page 2014

  28. [28]

    R. P. Stanley. A zonotope associated with graphical degree sequences. In Applied geometry and discrete mathematics, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 555--570. AMS, Providence, RI, 1991

    work page 1991

  29. [29]

    Sturmfels

    B. Sturmfels. Gr\"obner bases of toric varieties . Tohoku Mathematical Journal, 43 0 (2): 0 249 -- 261, 1991

    work page 1991

  30. [30]

    Sturmfels

    B. Sturmfels. Gr\" o bner bases and convex polytopes . University Lecture Series. American Mathematical Society, 1996

    work page 1996

  31. [31]

    Sturmfels

    B. Sturmfels. What is... a G r\"obner basis? Notices of the American Mathematical Society, 52: 0 1199--1200, 2005

    work page 2005

  32. [32]

    Sullivant

    S. Sullivant. Algebraic Statistics. Graduate Studies in Mathematics. American Mathematical Society, 2021

    work page 2021

  33. [33]

    R. R. Thomas. A geometric B uchberger algorithm for integer programming. Math. Oper. Res., 20 0 (4): 0 864--884, 1995

    work page 1995

  34. [34]

    R. H. Villarreal. Monomial Algebras. Chapman & Hall/CRC Monographs and Research Notes in Mathematics. CRC Press, 2018

    work page 2018