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

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ère-type parameters. Let $G(v,p)$ denote the usual Erdős-Rényi random graph on $v$ vertices with edge probability $p$. We obtain bounds for the expected value of the random variables $\mathrm{mr}(G(v,p))$, $\mathrm{M}(G(v,p))$, $\nu (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$.

17 pages, 2 figures