{
  "id": "1810.01551",
  "version": "v1",
  "published": "2018-10-03T00:52:03.000Z",
  "updated": "2018-10-03T00:52:03.000Z",
  "title": "A note on the largest bipartite subgraph in point-hyperplane incidence graphs",
  "authors": [
    "Thao T. Do"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given $m$ points and $n$ hyperplanes in $\\mathbb{R}^d$, if there are many incidences, we expect to find a big cluster $K_{r,s}$ in their incidence graph. Apfelbaum and Sharir found lower and upper bounds for the largest size of $rs$, which only match in three dimensions. In this paper we close the gap in four and five dimensions, up to some logarithmic factors.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-03T00:52:03.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "point-hyperplane incidence graphs",
      "largest bipartite subgraph",
      "big cluster",
      "upper bounds",
      "dimensions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}