{
  "id": "1501.00076",
  "version": "v1",
  "published": "2014-12-31T04:36:39.000Z",
  "updated": "2014-12-31T04:36:39.000Z",
  "title": "On The Number of Similar Instances of a Pattern in a Finite Set",
  "authors": [
    "Bernardo Abrego",
    "Silvia Fernandez-Merchant",
    "Daniel J. Katz",
    "Levon Kolesnikov"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "New bounds on the number of similar or directly similar copies of a pattern within a finite subset of the line or the plane are proved. The number of equilateral triangles whose vertices all lie within an $n$-point subset of the plane is shown to be no more than $\\lfloor{(4 n-1)(n-1)/18}\\rfloor$. The number of $k$-term arithmetic progressions that lie within an $n$-point subset of the line is shown to be at most $(n-r)(n+r-k+1)/(2 k-2)$, where $r$ is the remainder when $n$ is divided by $k-1$. This upper bound is achieved when the $n$ points themselves form an arithmetic progression, but for some values of $k$ and $n$, it can also be achieved for other configurations of the $n$ points, and a full classification of such optimal configurations is given. These results are achieved using a new general method based on ordering relations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-31T04:36:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C10",
      "05A15"
    ],
    "keywords": [
      "similar instances",
      "finite set",
      "point subset",
      "term arithmetic progressions",
      "full classification"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}