{
  "id": "1601.05058",
  "version": "v1",
  "published": "2016-01-19T20:01:04.000Z",
  "updated": "2016-01-19T20:01:04.000Z",
  "title": "Independent sets in polarity graphs",
  "authors": [
    "Michael Tait",
    "Craig Timmons"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a projective plane $\\Sigma$ and a polarity $\\theta$ of $\\Sigma$, the corresponding polarity graph is the graph whose vertices are the points of $\\Sigma$, and two distinct points $p_1$ and $p_2$ are adjacent if $p_1$ is incident to $p_2^{ \\theta}$ in $\\Sigma$. A well-known example of a polarity graph is the Erd\\H{o}s-R\\'{e}nyi orthogonal polarity graph $ER_q$, which appears frequently in a variety of extremal problems. Eigenvalue methods provide an upper bound on the independence number of any polarity graph. Mubayi and Williford showed that in the case of $ER_q$, the eigenvalue method gives the correct upper bound in order of magnitude. We prove that this is also true for other families of polarity graphs. This includes a family of polarity graphs for which the polarity is neither orthogonal nor unitary. We conjecture that any polarity graph of a projective plane of order $q$ has an independent set of size $\\Omega (q^{3/2})$. Some related results are also obtained.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-01-19T20:01:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "independent set",
      "eigenvalue method",
      "orthogonal polarity graph",
      "projective plane",
      "correct upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160105058T"
    }
  }
}