Skip to content
Preprint

Structural stability of systems and cycle covers in random graphs

Oct 2026 · 0 citations · 19 references
Mathematics

TL;DR

Together these results identify, for directed step-graphons, the regime in which a sampled topology is overwhelmingly likely or unlikely to sustain stable dynamics.

Abstract

Structural system theory studies which network topologies can sustain a prescribed system property such as controllability or stability. When the topology is itself random, the relevant question becomes probabilistic: how likely is a graph drawn from a stochastic model to sustain the property? Such probabilities measure the abundance and robustness of the property across topologies, and indicate whether systems requiring it can be reliably deployed in uncertain environments. We address this question for asymptotic stability of linear systems in the directed graphon setting. We consider two graph-theoretic properties. The first is $\mathcal N$, and it requires that for every $k\leq n$ some $k$-vertex induced subdigraph of $D$ admits a cycle cover, and the second is $\mathcal S$, which requires that these subdigraphs can be chosen so that their node sets form a nested sequence $V_1\subset\cdots\subset V_n=V(D)$ starting from a single vertex with a loop. We have shown that $\mathcal N$ is necessary and $\mathcal S$ is sufficient for structural stability. We sample $D$ from a directed step-graphon $W$. Our main results give necessary and sufficient conditions for $\Pr(\mathcal N)\to 1$ and $\Pr(\mathcal S)\to 1$ as $n\to\infty$. In more detail, to a step-graphon $W$ with skeleton digraph $S$ on $q$ nodes and concentration vector $x^*$ we associate a cycle polytope $\vec{\mathcal X}(S)\subseteq\Delta_q$. The conditions are then formulated in terms of the position of $x^*$ within $\vec{\mathcal X}(S)$, the dimension of the polytope, the loop density of $W$ and, for $\mathcal S$, an ordering condition on the cycles of the skeleton. Together these results identify, for directed step-graphons, the regime in which a sampled topology is overwhelmingly likely or unlikely to sustain stable dynamics.

View source

Similar papers

Preprint Oct 2026

P-stable degree sequence regions for bipartite and directed graphs

The switch Markov chain is a natural method for sampling graph realizations with a prescribed degree sequence, and $P$-stability is a general sufficient condition for its rapid mixing. Since $P$-stability is often difficult to verify directly, we develop an approach based on the simpler and more readily verifiable prop...

P. Erdös, Gábor Lippner, Na'ama Nevo et al. · 0 citations
Open access Oct 2026

Fault-tolerability analysis of hierarchical pancake networks based on 1-extra 3-component connectivity

The topology of interconnection networks is fundamental to the performance and reliability of parallel and distributed systems. Typically, an interconnection network is modeled as a graph, and connectivity of a graph serves as a critical parameter for measuring network reliability. The $h$-extra $r$-component vertex (r...

Run-Fa Yang, Shu-Min Zhang, Bo Zhu et al. · 0 citations
Open access Oct 2026

Bounds on the spectral radius of graphs via subgraph deletion and coalescence

The spectral radius of a graph is a fundamental parameter closelylinked to network dynamics and robustness. Understanding its precisevariation under structural perturbations such as vertex deletion,edge removal, or graph coalescence is a central problem in spectralgraph theory. In this paper, we establish several sharp...

Hongzhang Chen, Jian-Xi Li · 0 citations
Preprint Sep 2026

On splitting properties of the stability problem with integer choice functions

We consider the integer version of Alkan--Gale's model on stability in a two-sided market, called the stable generalized allocation one. It is given by a triple $(G,b,C)$, where $G=(V,E)$ is a finite bipartite graph with nonnegative integer capacities $b(e)\in{\mathbb Z}_+$ of edges $e\in E$, and for each vertex (``age...

A. Karzanov · 0 citations
Preprint Oct 2026

Product approximations for uniform spanning trees and determinantal processes

We prove that for every finite connected simple graph $G$ on $n$ vertices with minimum degree $k\geq 2$, there is a coupling of its uniform spanning tree and its random $1$-out subgraph under which the expected number of differing edges is $O(n\log (k)/\sqrt{k})$. More generally, we establish analogous couplings betwee...

A. Mészáros, Yuval Peled · 0 citations
Preprint Oct 2026

Local Convergence of Triadic Closures of Sparse Random Graphs

Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph $H$, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on $H$, each such pair is joined by an edge independently and simultaneous...

Himasish Talukdar · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.