The fixed-field Haemers number 
of an 
-vertex graph 
over a field 
is the minimum rank over all 
matrices 
over 
such that 
and 
if vertices 
and 
are not adjacent in 
. The Haemers number, denoted 
, 
(Alipour and Gohari 2023), or 
(Haemers 1978), is the minimum of 
over all fields 
. (Note that the critical word "not" was inadvertently
omitted in the original Haemers (1978) paper.)
The Haemers number is related to, but distinct from, the minimum rank of a graph. The latter requires symmetric matrices with an exact off-diagonal nonzero pattern, but does not require nonzero diagonal entries.
The Haemers number provides an upper bound on the Shannon capacity of 
which is sometimes better than the Lovász number.
For every field 
,
the independence number 
, fixed-field Haemers number, and clique
covering number 
satisfy
 |
(1)
|
Consequently,
 |
(2)
|
where 
is the chromatic number and 
denotes the graph complement
of 
(Haemers 1978). Indeed, the principal submatrix of a fitting matrix induced by an
independent set is diagonal with nonzero diagonal, giving the lower bound. For the
upper bound, a partition into 
cliques gives a fitting block matrix with one all-ones
block of rank one for each clique.
If 
is a perfect graph, then the perfect
graph theorem implies 
, so
 |
(3)
|
In particular, this equality holds for every bipartite graph. It also gives 
for the complete graph
and 
for the empty graph.
For every fixed field 
,
the fixed-field Haemers number is additive under the graph
union of pairwise vertex-disjoint graphs,
 |
(4)
|
This follows because every fitting matrix for a disjoint union is block diagonal, with one fitting block for each component. Minimizing over fields therefore gives
 |
(5)
|
Equality holds whenever a single field simultaneously attains all the component minima, in particular when every component value is independent of the field.
Since a complete multipartite graph 
is perfect and has independence
number 
,
 |
(6)
|
Consequently, the 
-vertex
Turán graph 
satisfies
![H(T(n,k))=[n/k].](/images/equations/HaemersNumber/NumberedEquation7.svg) |
(7)
|
The complement of a cycle graph of order 
satisfies
 |
(8)
|
For even 
,
the cycle and its complement are perfect, and 
. For odd 
, the upper bound follows from 
. For the lower bound, if a fitting matrix of rank
at most two were factored as 
, the zero entries corresponding to consecutive cycle
vertices would force row vectors 
and 
of 
to be proportional. Going around an odd cycle would make all
the 
proportional, contradicting the nonzero diagonal entries of 
.
