ELA, Volume 15, pp. 210-214, July 2006, abstract.

On Minimal Rank over Finite Fields

Guoli Ding and Andrei Kotlov 

Let F be a field.  Given a simple graph G on n vertices, 
its minimal rank (with respect to F) is the minimum rank of 
a symmetric n-by-n F-valued matrix whose off-diagonal zeroes 
are the same as in the adjacency matrix of G. If F is finite, 
then for every k, it is shown that the set of graphs of minimal 
rank at most k is characterized by finitely many forbidden 
induced subgraphs, each on at most ((|F|^k)/2+1)^2 vertices. 
These findings also hold in a more general context.