{
  "id": "2012.03938",
  "version": "v1",
  "published": "2020-12-06T06:59:05.000Z",
  "updated": "2020-12-06T06:59:05.000Z",
  "title": "The Local Structure of Bounded Degree Graphs",
  "authors": [
    "Yossi Rozantsev"
  ],
  "comment": "38 pages",
  "categories": [
    "math.CO",
    "cs.CC"
  ],
  "abstract": "Let $G=(V,E)$ be a simple graph with maximum degree $d$. For an integer $k\\in\\mathbb{N}$, the $k$-disc of a vertex $v\\in V$ is defined as the rooted subgraph of $G$ that is induced by all vertices whose distance to $v$ is at most $k$. The $k$-disc frequency distribution vector of $G$, denoted by $\\text{freq}_{k}(G)$, is a vector indexed by all isomorphism types of rooted $k$-discs. For each such isomorphism type $\\Gamma$, the corresponding entry in $\\text{freq}_{k}(G)$ counts the fraction of vertices in $V$ that have a $k$-disc isomorphic to $\\Gamma$. In a sense, $\\text{freq}_{k}(G)$ is one way to represent the \"local structure\" of $G$. The graph $G$ can be arbitrarily large, and so a natural question is whether given $\\text{freq}_{k}(G)$ it is possible to construct a small graph $H$, whose size is independent of $|V|$, such that $H$ has a similar local structure. N. Alon proved that for any $\\epsilon>0$ there always exists a graph $H$ whose size is independent of $|V|$ and whose frequency vector satisfies $||\\text{freq}_{k}(G)-\\text{freq}_{k}(H)||_{1}\\le\\epsilon$. However, his proof is only existential and does not imply that there is a deterministic algorithm to construct such a graph $H$. He gave the open problem of finding an explicit deterministic algorithm that finds $H$, or proving that no such algorithm exists. Our main result is that Alon's problem is undecidable if and only if a much more general problem (involving directed edges and edge colors) is undecidable. We also prove that both problems are decidable for the special case when $G$ is a path. We show that the local structure of any directed edge-colored path $G$ can be approximated by a suitable fixed-size directed edge-colored path $H$ and we give explicit bound on the size of $H$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-06T06:59:05.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded degree graphs",
      "fixed-size directed edge-colored path",
      "isomorphism type",
      "disc frequency distribution vector",
      "explicit deterministic algorithm"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}