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

Date
2010-07-01
Authors
Hall, H. Tracy
Hogben, Leslie
Hogben, Leslie
Martin, Ryan
Shader, Bryan
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
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 mr(G(v,p)), M(G(v,p)), ν(G(v,p)) and ξ(G(v,p)), which yield bounds on the average values of these parameters over all labeled graphs of order v.

Description
<p>This is a manuscript of an article from <em>Linear Algebra and its Applications</em> 433 (2010): 401, doi:<a href="http://dx.doi.org/10.1016/j.laa.2010.01.036" target="_blank">10.1016/j.laa.2010.01.036</a>. Posted with permission.</p>
Keywords
Minimum rank, Maximum nullity, Average minimum rank, Average maximum nullity, Expected value, Colin de Verdière type parameter, Positive semidefinite minimum rank, Delta conjecture, Rank, Matrix, Random graph, Graph
Citation
Collections