On a Conjecture of Godsil Concerning Controllable Random Graphs
From MaRDI portal
Abstract: It is conjectured by Godsil that the relative number of controllable graphs compared to the total number of simple graphs on n vertices approaches one as n tends to infinity. We prove that this conjecture is true. More generally, our methods show that the linear system formed from the pair (W, b) is controllable for a large class of Wigner random matrices W and deterministic vectors b. The proof relies on recent advances in Littlewood-Offord theory developed by Rudelson and Vershynin.
Recommendations
- Further results on almost controllable graphs
- Controllability and matchings in random bipartite graphs
- Further results on controllable graphs
- On Pósa's conjecture for random graphs
- The controllability of graphs with diameter 0-2
- Controllability of undirected graphs
- On the concentration of the domination number of the random graph
- An analogue of the Erdős-Gallai theorem for random graphs
- Tuza's conjecture for random graphs
- On the domination number of a random graph
Cites work
- Additive combinatorics
- Controllability Metrics, Limitations and Algorithms for Complex Networks
- Controllability of multi-agent systems from a graph-theoretic perspective
- Controllability, identification, and randomness in distributed systems
- Controllable subsets in graphs
- Fully parallel 3D thinning algorithms based on sufficient conditions for topology preservation
- Gramian-Based Reachability Metrics for Bilinear Networks
- Graph Controllability Classes for the Laplacian Leader-Follower Dynamics
- scientific article; zbMATH DE number 3181381 (Why is no real title available?)
- scientific article; zbMATH DE number 741240 (Why is no real title available?)
- scientific article; zbMATH DE number 3242549 (Why is no real title available?)
- scientific article; zbMATH DE number 3331185 (Why is no real title available?)
- Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
- Invertibility of symmetric random matrices
- Laplacian controllability classes for threshold graphs
- Linear systems theory.
- Minimal Controllability Problems
- No-gaps delocalization for general random matrices
- On the Controllability Properties of Circulant Networks
- On the distribution of the roots of certain symmetric matrices
- Probability: A Graduate Course
- Random matrices have simple spectrum
- Random matrices: tail bounds for gaps between eigenvalues
- Small ball probability, inverse theorems, and applications
- Smallest singular value of a random rectangular matrix
- Some estimates of norms of random matrices
- The Littlewood-Offord problem and invertibility of random matrices
Cited in
(41)- Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
- New families of graphs determined by their generalized spectrum
- Low-degree factors of random polynomials
- Note on graphs with irreducible characteristic polynomials
- Graphs with \(n - 1\) main eigenvalues
- Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
- Unlocking the walk matrix of a graph
- Partial strong structural controllability
- A new criterion for almost controllable graphs being determined by their generalized spectra
- On a theorem of Godsil and McKay concerning the construction of cospectral graphs
- Controllability, matching ratio and graph convergence
- The polynomial reconstruction problem: the first 50 years
- Controllability and matchings in random bipartite graphs
- A simple arithmetic criterion for graphs being determined by their generalized spectra
- Eigenvectors of random matrices of symmetric entry distributions
- Pairing between zeros and critical points of random polynomials with independent roots
- How to suppress dark states in quantum networks and bio-engineered structures
- scientific article; zbMATH DE number 7342370 (Why is no real title available?)
- On stable systems with random structure
- Random matrices and controllability of dynamical systems
- A note on non-\(\mathbb{R}\)-cospectral graphs
- A Survey of Determinacy of Infinite Games in Second Order Arithmetic
- On the smallest singular value of symmetric random matrices
- Spectral multiplicity functions of adjacency operators of graphs and cospectral infinite graphs
- Canonization of a random circulant graph by counting walks
- On verification and design of input matrix for robust linear systems: complexity and polynomially solvable cases
- On the generalized spectral characterizations of Eulerian graphs
- The overgraphs of generalized cospectral controllable graphs
- On the determinant of the walk matrix of the rooted product with a path
- Cokernel statistics for walk matrices of directed and weighted random graphs
- Generalized spectral characterizations of almost controllable graphs: revisited
- Counting cospectral graphs obtained via switching
- On a hierarchy of spectral isomorphism invariants
- A characterization of generalized cospectrality of rooted graphs with applications in graph reconstruction
- On a hierarchy of spectral invariants for graphs
- Which graphs are determined by their total number of walks?
- Primary decomposition theorem and generalized spectral characterization of graphs
- Haemers’ Conjecture: An Algorithmic Perspective
- Quantum state transfer in graphs with tails
- A general formula for walk determinants of rooted products with applications to DGS-graph constructions
- Generalized block diagonal Laplacian spectrum of graphs
This page was built for publication: On a Conjecture of Godsil Concerning Controllable Random Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2953321)
