{
  "id": "1404.6261",
  "version": "v1",
  "published": "2014-04-24T20:06:58.000Z",
  "updated": "2014-04-24T20:06:58.000Z",
  "title": "On sets of integers with restrictions on their products",
  "authors": [
    "Michael Tait",
    "Jacques Verstraete"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A {\\em product-injective labeling} of a graph $G$ is an injection $\\chi: V(G) \\to \\mathbb{Z}$ such that $\\chi(u)\\chi(v) \\not= \\chi(x)\\chi(y)$ for any distinct edges $uv, xy\\in E(G)$. Let $P(G)$ be the smallest $N \\geq 1$ such that there exists a product-injective labeling $\\chi : V(G) \\rightarrow [N]$. Let $P(n,d)$ be the maximum possible value of $P(G)$ over $n$-vertex graphs $G$ of maximum degree at most $d$. In this paper, we determine the asymptotic value of $P(n,d)$ for all but a small range of values of $d$ relative to $n$. Specifically, we show that there exist constants $a,b > 0$ such that $P(n,d) \\sim n$ if $d \\leq \\sqrt{n}(\\log n)^{-a}$ and $P(n,d) \\sim n\\log n$ if $d \\geq \\sqrt{n}(\\log n)^{b}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-24T20:06:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "restrictions",
      "maximum degree",
      "small range",
      "distinct edges",
      "asymptotic value"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.6261T"
    }
  }
}