Structural stability of systems and cycle covers in random graphs

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 𝒩, and it requires that for every k≤ n some k-vertex induced subdigraph of D admits a cycle cover, and the second is 𝒮, which requires that these subdigraphs can be chosen so that their node sets form a nested sequence V₁⊂⋯⊂ V_n=V(D) starting from a single vertex with a loop. We have shown that 𝒩 is necessary and 𝒮 is sufficient for structural stability. We sample D from a directed step-graphon W. Our main results give necessary and sufficient conditions for Pr(𝒩)→ 1 and Pr(𝒮)→ 1 as n→∞. In more detail, to a step-graphon W with skeleton digraph S on q nodes and concentration vector x^* we associate a cycle polytope 𝒳⃗(S)⊆Δ_q. The conditions are then formulated in terms of the position of x^* within 𝒳⃗(S), the dimension of the polytope, the loop density of W and, for 𝒮, 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.

Exact three-component covers in 2-coloured random bipartite graphs
Xiao-Chuan Liu, Xu Yang
arXiv1 Sep 2026PreprintCC0Full textCombinatorics & discrete mathematicsarXiv
On the Stability of the Independence Number in Random Distance Graphs
Vsevolod A. Pokhachevskiy, Andrei Raigorodskii
arXiv8 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
Degree Stability of Parallel Greedy Matching in Random Graphs
Vishvajeet N, Shrinidhi Teganahally Sridhara
arXiv18 Oct 2026PreprintCC BY-SA 4.0Full textProbabilityarXiv
Universality in random graphs via optimal linking systems: trees and beyond
Asaf Cohen Antonir, Lyuben Lichev, Maksim Zhukovskii
arXiv2 Nov 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics ProbabilityarXiv
Generic Structural Stability for Riemann Solutions to n × n Systems of Hyperbolic Conservation Laws
Hong Kiat Tan, Andrea L. Bertozzi
arXiv23 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Dynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{belabbas2026structural,
  title = {{Structural stability of systems and cycle covers in random graphs}},
  author = {Mohamed Ali Belabbas},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01607},
  eprint = {2610.01607},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01607},
}

RIS

TY  - UNPB
TI  - Structural stability of systems and cycle covers in random graphs
AU  - Mohamed Ali Belabbas
PY  - 2026
DA  - 2026/10/01
PB  - arXiv
DO  - 10.48550/arxiv.2610.01607
UR  - https://arxiv.org/abs/2610.01607
AB  - 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 𝒩, and it requires that for every k≤ n some k-vertex induced subdigraph of D admits a cycle cover, and the second is 𝒮, which requires that these subdigraphs can be chosen so that their node sets form a nested sequence V_1⊂⋯⊂ V_n=V(D) starting from a single vertex with a loop. We have shown that 𝒩 is necessary and 𝒮 is sufficient for structural stability. We sample D from a directed step-graphon W. Our main results give necessary and sufficient conditions for Pr(𝒩)→ 1 and Pr(𝒮)→ 1 as n→∞. In more detail, to a step-graphon W with skeleton digraph S on q nodes and concentration vector x^* we associate a cycle polytope 𝒳⃗(S)⊆Δ_q. The conditions are then formulated in terms of the position of x^* within 𝒳⃗(S), the dimension of the polytope, the loop density of W and, for 𝒮, 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.
ER  -

Abstract

Related

Cite