-
Probabilistic Zero Forcing with Vertex Reversion
Authors:
Zachary Brennan
Abstract:
Probabilistic zero forcing is a graph coloring process in which blue vertices "infect" (color blue) white vertices with a probability proportional to the number of neighboring blue vertices. We introduce reversion probabilistic zero forcing (RPZF), which shares the same infection dynamics but also allows for blue vertices to revert to being white in each round. We establish a tool which, given a g…
▽ More
Probabilistic zero forcing is a graph coloring process in which blue vertices "infect" (color blue) white vertices with a probability proportional to the number of neighboring blue vertices. We introduce reversion probabilistic zero forcing (RPZF), which shares the same infection dynamics but also allows for blue vertices to revert to being white in each round. We establish a tool which, given a graph's RPZF Markov transition matrix, calculates the probability that the graph turns all white or all blue as well as the time at which this is expected to occur. For specific graph families we produce a threshold number of blue vertices for the graph to become entirely blue in the next round with high probability.
△ Less
Submitted 23 April, 2024;
originally announced April 2024.
-
Power domination with random sensor failure
Authors:
Beth Bjorkman,
Zachary Brennan,
Mary Flagg,
Johnathan Koch
Abstract:
The power domination problem seeks to determine the minimum number of phasor measurement units (PMUs) needed to monitor an electric power network. We introduce random sensor failure before the power domination process occurs and call this the fragile power domination process. For a given graph, PMU placement, and probability of PMU failure $q$, we study the expected number of observed vertices at…
▽ More
The power domination problem seeks to determine the minimum number of phasor measurement units (PMUs) needed to monitor an electric power network. We introduce random sensor failure before the power domination process occurs and call this the fragile power domination process. For a given graph, PMU placement, and probability of PMU failure $q$, we study the expected number of observed vertices at the termination of the fragile power domination process. This expected value is a polynomial in $q$, which we relate to fault-tolerant and PMU-defect-robust power domination. We also study the probability of that the entire graph becomes observed and give results for some graph families.
△ Less
Submitted 19 December, 2023;
originally announced December 2023.
-
Orthogonal realizations of random sign patterns and other applications of the SIPP
Authors:
Zachary Brennan,
Christopher Cox,
Bryan A. Curtis,
Enrique Gomez-Leos,
Kimberly P. Hadaway,
Leslie Hogben,
Conor Thompson
Abstract:
A sign pattern is an array with entries in $\{+,-,0\}$. A matrix $Q$ is row orthogonal if $QQ^T = I$. The Strong Inner Product Property (SIPP), introduced in [B.A.~Curtis and B.L.~Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228--259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because…
▽ More
A sign pattern is an array with entries in $\{+,-,0\}$. A matrix $Q$ is row orthogonal if $QQ^T = I$. The Strong Inner Product Property (SIPP), introduced in [B.A.~Curtis and B.L.~Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228--259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because it guarantees there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry. This paper uses the SIPP to initiate the study of conditions under which random sign patterns allow row orthogonality with high probability. Building on prior work, $5\times n$ nowhere zero sign patterns that minimally allow orthogonality are determined. Conditions on zero entries in a sign pattern are established that guarantee any row orthogonal matrix with such a sign pattern has the SIPP.
△ Less
Submitted 10 December, 2022;
originally announced December 2022.
-
Cutoff in the Bernoulli-Laplace model with $O(n)$ swaps
Authors:
Joseph S. Alameda,
Caroline Bang,
Zachary Brennan,
David P. Herzog,
Jürgen Kritschgau,
Elizabeth Sprangel
Abstract:
This paper considers the $(n,k)$-Bernoulli--Laplace model in the case when there are two urns, the total number of red and white balls is the same, and the number of selections $k$ at each step is on the same asymptotic order as the number of balls $n$ in each urn. Our main focus is on the large-time behavior of the corresponding Markov chain tracking the number of red balls in a given urn. Under…
▽ More
This paper considers the $(n,k)$-Bernoulli--Laplace model in the case when there are two urns, the total number of red and white balls is the same, and the number of selections $k$ at each step is on the same asymptotic order as the number of balls $n$ in each urn. Our main focus is on the large-time behavior of the corresponding Markov chain tracking the number of red balls in a given urn. Under reasonable assumptions on the asymptotic behavior of the ratio $k/n$ as $n\rightarrow \infty$, cutoff in the total variation distance is established. A cutoff window is also provided. These results, in particular, partially resolve an open problem posed by Eskenazis and Nestoridi.
△ Less
Submitted 17 March, 2022; v1 submitted 16 March, 2022;
originally announced March 2022.
