{
  "id": "2003.01571",
  "version": "v1",
  "published": "2020-03-03T15:07:44.000Z",
  "updated": "2020-03-03T15:07:44.000Z",
  "title": "Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph",
  "authors": [
    "Alexandr Valyuzhenich"
  ],
  "comment": "14 pages, 4 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The Hamming graph $H(n,q)$ is the graph whose vertices are the words of length $n$ over the alphabet $\\{0,1,\\ldots,q-1\\}$, where two vertices are adjacent if they differ in exactly one coordinate. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\\cdot i$ with corresponding eigenspaces $U_{i}(n,q)$ for $0\\leq i\\leq n$. In this work we study functions belonging to a direct sum $U_i(n,q)\\oplus U_{i+1}(n,q)\\oplus\\ldots\\oplus U_j(n,q)$ for $0\\leq i\\leq j\\leq n$. We find the minimum cardinality of the support of such functions for $q=2$ and for $q=3$, $i+j>n$. In particular, we find the minimum cardinality of the support of eigenfunctions from the eigenspace $U_{i}(n,3)$ for $i>\\frac{n}{2}$. Using the correspondence between $1$-perfect bitrades and eigenfunctions with eigenvalue $-1$, we find the minimum size of a $1$-perfect bitrade in the Hamming graph $H(n,3)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-03-03T15:07:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamming graph",
      "eigenfunctions",
      "perfect bitrade",
      "minimum cardinality",
      "eigenspace"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}