{
  "id": "1702.08579",
  "version": "v1",
  "published": "2017-02-27T23:26:18.000Z",
  "updated": "2017-02-27T23:26:18.000Z",
  "title": "Maximum Size of a Family of Pairwise Graph-Different Permutations",
  "authors": [
    "Louis Golowich",
    "Chiheon Kim",
    "Richard Zhou"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Two permutations of the vertices of a graph $G$ are called $G$-different if there exists an index $i$ such that $i$-th entry of the two permutations form an edge in $G$. We bound or determine the maximum size of a family of pairwise $G$-different permutations for various graphs $G$. We show that for all balanced bipartite graphs $G$ of order $n$ with minimum degree $n/2 - o(n)$, the maximum number of pairwise $G$-different permutations of the vertices of $G$ is $2^{(1-o(1))n}$. We also present examples of bipartite graphs $G$ with maximum degree $O(\\log n)$ that have this property. We explore the problem of bounding the maximum size of a family of pairwise graph-different permutations when an unlimited number of disjoint vertices is added to a given graph. We determine this exact value for the graph of 2 disjoint edges, and present some asymptotic bounds relating to this value for graphs consisting of the union of $n/2$ disjoint edges.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-02-27T23:26:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "pairwise graph-different permutations",
      "maximum size",
      "disjoint edges",
      "exact value",
      "asymptotic bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}