Expected values of parameters associated with the minimum rank of a graph

DOI10.1016/J.LAA.2010.01.036MaRDI QIDQ972786zbMATH OpenOpenAlexFDO

Authors H. Tracy Hall, Leslie Hogben, Ryan R. Martin, Bryan L. Shader

Publication date 21 May 2010

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.05692, https://lib.dr.iastate.edu/math_pubs/67

zbMATH Keywords

graphrankrandom graphmatrixexpected valuemaximum nullityminimum rankpositive semidefinite minimum rankdelta conjectureaverage maximum nullityaverage minimum rankColin de Verdière type parameter

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/maximum nullity and related Colin de Verdi`ere-type parameters. Let $G(v,p)$ denote the usual ErdH{o}s-R'enyi random graph on $v$ vertices with edge probability $p$. We obtain bounds for the expected value of the random variables $mmr(G(v,p))$, $mM(G(v,p))$, $u(G(v,p))$ and $xi(G(v,p))$, which yield bounds on the average values of these parameters over all labeled graphs of order $v$.

Recommendations

• The minrank of random graphs
• The Minrank of Random Graphs
• The minrank of random graphs over arbitrary fields
• Expected rank and randomness in rooted graphs
• The rank of random graphs
• Kneser ranks of random graphs and minimum difference representations
• Kneser ranks of random graphs and minimum difference representations
• The expected value of random minimal length spanning tree of a complete graph
• Rank-width of random graphs
• scientific article; zbMATH DE number 2066194

Cites work

• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 1303522 (Why is no real title available?)
• scientific article; zbMATH DE number 475583 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A correction: Orthogonal representations and connectivity of graphs
• A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
• An upper bound for the minimum rank of a graph
• Degree sequences of random graphs
• Multiplicities of eigenvalues and tree-width of graphs
• On the number of zero-patterns of a sequence of polynomials
• On the relation between two minor-monotone graph parameters
• Orthogonal representations and connectivity of graphs
• Paths in graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• The minimum rank of symmetric matrices described by a graph: a survey
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Three-connected graphs whose maximum nullity is at most three

Cited in

(14)

• An integer program for positive semidefinite zero forcing in graphs
• Expected value of the minimal basis of random matroid and distributions of q-analogs of order statistics
• The extremal function and Colin de Verdière graph parameter
• Note on von Neumann and Rényi entropies of a graph
• The (minimum) rank of typical fooling-set matrices
• Maximum generic nullity of a graph
• The Zero Forcing Number of Graphs
• Approximating the minimum rank of a graph via alternating projection
• On the minimum rank of a graph over finite fields
• Expected rank in antimatroids
• On graphs of minimum skew rank 4
• The Minrank of Random Graphs
• The minrank of random graphs
• Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph

This page was built for publication: Expected values of parameters associated with the minimum rank of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972786)