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

DOI10.1016/J.LAA.2010.01.036zbMATH Open1217.05142arXiv1605.05692OpenAlexW1966863811MaRDI QIDQ972786FDOQ972786

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

Publication date: 21 May 2010

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

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$.

Full work available at URL: https://arxiv.org/abs/1605.05692

zbMATH Keywords

graphrankrandom graphmatrixexpected value[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Colin+de+Verdi%EF%BF%BD%EF%BF%BDre+type+parameter&go=Go Colin de Verdi��re type parameter]maximum nullityminimum rankpositive semidefinite minimum rankdelta conjectureaverage maximum nullityaverage minimum rank

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)

Cites Work

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

Cited In (14)

• 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
• The (minimum) rank of typical fooling-set matrices
• Note on von Neumann and Rényi entropies of a graph
• 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
• An integer program for positive semidefinite zero forcing in graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• The rank of random graphs 👍 👎
• Rank-width of random graphs 👍 👎
• The minrank of random graphs over arbitrary fields 👍 👎
• Kneser ranks of random graphs and minimum difference representations 👍 👎
• Expected rank and randomness in rooted graphs 👍 👎
• The expected value of random minimal length spanning tree of a complete graph 👍 👎
• The Minrank of Random Graphs 👍 👎
• Kneser Ranks of Random Graphs and Minimum Difference Representations 👍 👎
• The minrank of random graphs 👍 👎

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)