The Minrank of Random Graphs over Arbitrary Fields

Noga Alon, Igor Balla, Lior Gishboliner +2

The minrank of a graph $G$ on the set of vertices $[n]$ over a field $\mathbb{F}$ is the minimum possible rank of a matrix $M\in {\mathbb{F}}^{n\times n}$ with nonzero diagonal entrie…