{
  "id": "1807.09139",
  "version": "v1",
  "published": "2018-07-24T14:15:32.000Z",
  "updated": "2018-07-24T14:15:32.000Z",
  "title": "Minimum supports of functions on the Hamming graphs with spectral constrains",
  "authors": [
    "Alexandr Valyuzhenich",
    "Konstantin Vorob'ev"
  ],
  "comment": "18 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study functions defined on the vertices of the Hamming graphs $H(n,q)$. 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 consider the problem of finding the minimum possible support (the number of nonzeros) of 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$. For the case $n\\geq i+j$ and $q\\geq 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $n<i+j$ and $q\\geq 4$ we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for $i=j$, $n<2i$ and $q\\geq 5$. In particular, we characterize eigenfunctions from the eigenspace $U_{i}(n,q)$ with the minimum cardinality of the support for cases $i\\le \\frac{n}{2}$,$q\\ge 3$ and $i> \\frac{n}{2}$,$\\,q\\ge 5$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-24T14:15:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50"
    ],
    "keywords": [
      "minimum cardinality",
      "hamming graphs",
      "minimum supports",
      "spectral constrains",
      "adjacency matrix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}