pith. sign in

arxiv: 1906.11083 · v1 · pith:6M4MOBSVnew · submitted 2019-06-25 · 🧮 math.CO

Using Markov chains to determine expected propagation time for probabilistic zero forcing

Yu Chan , Emelie Curl , Jesse Geneson , Leslie Hogben , Kevin Liu , Issac Odegard , Michael S. Ross This is my paper

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

classification 🧮 math.CO
keywords probabilistic zero forcingMarkov chainsexpected propagation timezero forcinggraph coloringabsorption timecolor-change rule
0
0 comments X

The pith

Given a Markov transition matrix for probabilistic zero forcing, there is an exact formula for expected propagation time.

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

The paper models probabilistic zero forcing as a Markov chain whose states track which vertices are blue. From the transition matrix of this chain, it derives an exact formula for the expected time to reach the all-blue absorbing state. This gives a precise way to compute average propagation time on any connected graph instead of using only simulations or loose bounds. The same matrix method is then applied to obtain bounds on the expected time for various families of graphs.

Core claim

Given a Markov transition matrix for a probabilistic zero forcing process, the expected propagation time equals the absorption time of the chain and is given by an exact closed-form expression obtained directly from the matrix entries.

What carries the argument

The Markov transition matrix of the probabilistic zero forcing process, which encodes the probability of each possible color-change step between subsets of blue vertices and determines the expected steps to absorption at the full-blue state.

If this is right

  • The exact expected time can be computed for any specific graph by building its transition matrix and solving the resulting linear system.
  • Bounds on expected propagation time follow for infinite families of graphs once their matrices are analyzed.
  • The method supplies a uniform computational framework for studying average duration across all connected graphs.

Where Pith is reading between the lines

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

  • The same matrix approach could be used to compare expected times across different initial blue sets and identify which sets minimize average coloring time.
  • The formula might extend to variants of zero forcing that use different probability rules for the color-change step.
  • One could compute higher moments of the propagation time distribution, not just the expectation, from the same transition matrix.

Load-bearing premise

The probabilistic zero forcing process on a connected graph can be accurately represented as a finite-state Markov chain whose transition matrix fully captures the color-change probabilities and whose absorption time yields the propagation time.

What would settle it

Construct the transition matrix for probabilistic zero forcing on a 4-cycle, compute the formula's expected time, then run thousands of direct simulations and check whether the sample average matches the formula value within sampling error.

Figures

Figures reproduced from arXiv: 1906.11083 by Emelie Curl, Issac Odegard, Jesse Geneson, Kevin Liu, Leslie Hogben, Michael S. Ross, Yu Chan.

Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

Zero forcing is a coloring game played on a graph where each vertex is initially colored blue or white and the goal is to color all the vertices blue by repeated use of a (deterministic) color change rule starting with as few blue vertices as possible. Probabilistic zero forcing yields a discrete dynamical system governed by a Markov chain. Since in a connected graph any one vertex can eventually color the entire graph blue using probabilistic zero forcing, the expected time to do this studied. Given a Markov transition matrix for a probabilistic zero forcing process, we establish an exact formula for expected propagation time. We apply Markov chains to determine bounds on expected propagation time for various families of graphs.

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

0 major / 3 minor

Summary. The manuscript models the probabilistic zero forcing process on a connected graph as an absorbing Markov chain whose states are subsets of blue vertices (with the full vertex set as the unique absorbing state). It states an exact formula for the expected propagation time (expected absorption time) in terms of the transient submatrix Q of the transition matrix, and applies the resulting expression to obtain bounds on this quantity for several families of graphs.

Significance. If the modeling and formula application are correct, the work supplies a systematic, computable expression for expected propagation time that follows directly from standard absorbing Markov chain theory. This is a clear strength for reproducibility and allows explicit calculations or bounds once the transition probabilities are fixed. The approach may be useful for comparing probabilistic zero forcing to its deterministic counterpart on concrete graph classes.

minor comments (3)
  1. The abstract and introduction should explicitly write the claimed formula (e.g., t = (I - Q)^{-1} 1) rather than only asserting its existence, so readers can immediately verify it matches the standard fundamental-matrix result.
  2. Section describing the Markov chain construction should include a brief verification that the chain is absorbing on connected graphs (single absorbing state reachable from every transient state) to make the application of the formula fully self-contained.
  3. When bounds are derived for specific graph families, the manuscript should state whether the bounds are obtained by direct matrix inversion on small instances or by analytic estimates on the entries of (I - Q)^{-1}; this distinction affects how the results can be extended.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central claim is an exact formula for expected propagation time given the Markov transition matrix of the probabilistic zero forcing process. This reduces directly to the standard linear algebra result for expected absorption time in an absorbing Markov chain (t = (I - Q)^{-1} 1), which is external textbook mathematics and not derived from any self-citation, fitted parameter, or ansatz internal to the paper. The modeling assumptions (finite state space on subsets of blue vertices, absorption at the full set for connected graphs) are the conventional ones and introduce no self-referential step. No load-bearing self-citation or renaming of known results occurs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; full derivation and any hidden parameters or assumptions are unavailable.

axioms (1)
  • domain assumption Probabilistic zero forcing yields a discrete dynamical system governed by a Markov chain.
    Explicitly stated in the abstract as the modeling premise.

pith-pipeline@v0.9.0 · 5651 in / 1155 out tokens · 40736 ms · 2026-05-25T16:16:52.310903+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

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

  1. [1]

    Barioli, W

    AIM Minimum Rank – Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. M. Cioaba, D. Cvetkovi´ c, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovi´ c, H. van der Holst, K. Vander Meulen, A. Wangsness). Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl.,...

    work page 2008

  2. [2]

    Benson, D

    K.F. Benson, D. Ferrero, M. Flagg, V. Furst, L. Hogben, V. Vasilevska, B. Wissman. Zero forcing and power domination for graph products. Australasian J . Combinatorics 70 (2018), 221–235

    work page 2018

  3. [3]

    Burgarth, V

    D. Burgarth, V. Giovannetti. Full control by locally induced relaxation. Phys. Rev. Lett. PRL 99 (2007), 100501

    work page 2007

  4. [4]

    Burgarth, K

    D. Burgarth, K. Maruyama. Indirect Hamiltonian identification through a small gateway. New J. Phys. NJP 11 (2009) 103019. 15

    work page 2009

  5. [5]

    Butler, M

    S. Butler, M. Young. Throttling zero forcing propagation speed on graphs. Australas. J. Combin., 57 (2013), 65–71

    work page 2013

  6. [6]

    Y. Chan. Appendix 1: Expected propagation time for graphs of orders 4, 5, 6, and 7. PDF available at https://aimath. org/∼hogben/ISU/Appendix1.pdf. Sage worksheet published at https://sage.math.iastate.edu/home/pub/118/

    work page

  7. [7]

    Chilakamarri, N

    K. Chilakamarri, N. Dean, C.X. Kang, E. Yi. Iteration Index of a Zero Forcing Set in a Graph. Bull. Inst. Combin. Appl. 64 (2012) 57–72

    work page 2012

  8. [8]

    Graph theory, fourth

    R Diestel. Graph theory, fourth. ed. Graduate Texts in Mathematics, Springer, Heidelberg, 2010

    work page 2010

  9. [9]

    Fallat, L

    S.M. Fallat, L. Hogben. The minimum rank of symmetric matrices described by a graph: A survey. Linear Algebra Appl. 426 (2007) 558–582

    work page 2007

  10. [10]

    Fallat and L

    S. Fallat and L. Hogben. Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs. In Handbook of Linear Algebra, 2nd edition, L. Hogben editor, CRC Press, Boca Raton, 2014

    work page 2014

  11. [11]

    Propagation time for probabilistic zero forcing

    J. Geneson, L. Hogben. Propagation time for probabilistic zero forcing. https://arxiv.org/abs/1812.10476

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    Hogben, M

    L. Hogben, M. Huynh, N. Kingsley, S. Meyer, S. Walker, M. Young. Propagation time for zero forcing on a graph. Discrete Appl. Math. 160 (2012) 1994–2005

    work page 2012

  13. [13]

    Horn, C.R

    R.A. Horn, C.R. Johnson. Matrix Analysis, 2nd ed. Cambridge University Press, New York, 2013

    work page 2013

  14. [14]

    C.X. Kang, E. Yi. Probabilistic zero forcing in graphs. Bull. Inst. Combin. Appl. 67 (2013), 9–16

    work page 2013

  15. [15]

    K. Liu. Appendix 2: Expected propagation time for comb-graphs. PDF available at https://aimath.org/ ∼hogben/ISU/ Appendix2.pdf. Sage worksheet for combs and suns published at https://sage.math.iastate.edu/home/pub/119/

    work page

  16. [16]

    Warnberg

    N. Warnberg. Positive semidefinite propagation time. Discrete Appl. Math. , 198 (2016) 274–290

    work page 2016

  17. [17]

    B. Yang. Fast-mixed searching and related problems on graphs. Theoret. Comput. Sci. 507 (2013), 100–113. 16

    work page 2013