{
  "id": "1006.0770",
  "version": "v2",
  "published": "2010-06-04T02:43:26.000Z",
  "updated": "2010-07-20T18:19:17.000Z",
  "title": "On the minimum rank of a graph over finite fields",
  "authors": [
    "Shmuel Friedland",
    "Raphael Loewy"
  ],
  "comment": "16 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper we deal with two aspects of the minimum rank of a simple undirected graph $G$ on $n$ vertices over a finite field $\\FF_q$ with $q$ elements, which is denoted by $\\mr(\\FF_q,G)$. In the first part of this paper we show that the average minimum rank of simple undirected labeled graphs on $n$ vertices over $\\FF_2$ is $(1-\\varepsilon_n)n$, were $\\lim_{n\\to\\infty} \\varepsilon_n=0$. In the second part of this paper we assume that $G$ contains a clique $K_k$ on $k$-vertices. We show that if $q$ is not a prime then $\\mr(\\FF_q,G)\\le n-k+1$ for $4\\le k\\le n-1$ and $n\\ge 5$. It is known that $\\mr(\\FF_q,G)\\le 3$ for $k=n-2$, $n\\ge 4$ and $q\\ge 4$. We show that for $k=n-2$ and each $n\\ge 10$ there exists a graph $G$ such that $\\mr(\\FF_3,G)>3$. For $k=n-3$, $n\\ge 5$ and $q\\ge 4$ we show that $\\mr(\\FF_q,G)\\le 4$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-07-20T18:19:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "11T99",
      "15A03"
    ],
    "keywords": [
      "finite field",
      "average minimum rank",
      "first part",
      "simple undirected graph",
      "simple undirected labeled graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1006.0770F"
    }
  }
}