On the minimum rank of a graph

Abstract

The minimum rank of a graph $G$ over a field $\F$ is the smallest possible rank of an $n\times n$ symmetric matrix whose $(i,j)$-entry is nonzero if and only if two vertices $i$ and $j$ are adjacent in $G$ for $i\neq j$. A random graph $G(n,p)$ is a graph on a vertex set $\{1,2,\cdots,n\}$ such that two vertices are adjacent independently at random with probability $p$. First, we investigate the minimum rank of a random graph over the binary field $\F_2$. We prove that the minimum rank of a random graph $G(n,1/2)$ over the binary field is at least $n-\sqrt{2n}-1.1$ asymptotically almost surely. Also, we prove that if $p(n)$ is a function such that $0<p(n)\le\frac{1}{2}$ and $np(n)$ is increasing, then the minimum rank of a random graph $G(n,p(n))$ over the binary field is at least $n-1.178\sqrt{n/p(n)}$ asymptotically almost surely. Second, we show that for a fixed positive integer $k$ and a fixed finite field $\F_q$, there exists $O(\abs{V(G)}^2)$-time algorithm that decides whether the input graph $G$ has the minimum rank over $\F_q$ at most $k$. We have three different proofs using a monadic second-order logic, dynamic programming, or a kernelization.