{
  "id": "2504.16265",
  "version": "v2",
  "published": "2025-04-22T20:56:33.000Z",
  "updated": "2025-05-16T11:24:49.000Z",
  "title": "Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies",
  "authors": [
    "Søren Riis"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We introduce \\emph{Term Coding}, a novel framework for analysing extremal problems in discrete mathematics by encoding them as finite systems of \\emph{term equations} (and, optionally, \\emph{non-equality constraints}). In its basic form, all variables range over a single domain, and we seek an interpretation of the function symbols that \\emph{maximises} the number of solutions to these constraints. This perspective unifies classical questions in extremal combinatorics, network/index coding, and finite model theory. We further develop \\emph{multi-sorted Term Coding}, a more general approach in which variables may be of different sorts (e.g., points, lines, blocks, colours, labels), possibly supplemented by variable-inequality constraints to enforce distinctness. This extension captures sophisticated structures such as block designs, finite geometries, and mixed coding scenarios within a single logical formalism. Our main result shows how to determine (up to a constant) the maximum number of solutions \\(\\max_{\\mathcal{I}}(\\Gamma,n)\\) for any system of term equations (possibly including non-equality constraints) by relating it to \\emph{graph guessing numbers} and \\emph{entropy measures}. Finally, we focus on \\emph{dispersion problems}, an expressive subclass of these constraints. We discover a striking complexity dichotomy: deciding whether, for a given integer \\(r\\), the maximum code size that reaches \\(n^{r}\\) is \\emph{undecidable}, while deciding whether it exceeds \\(n^{r}\\) is \\emph{polynomial-time decidable}.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2025-05-16T11:24:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q17",
      "05C85",
      "94A24",
      "03C13",
      "F.1.3",
      "G.2.2",
      "E.4"
    ],
    "keywords": [
      "extremal combinatorics",
      "complexity dichotomy",
      "term coding",
      "constraints",
      "dispersion"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}