Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914072825430016 |
|---|---|
| author | Riis, Søren |
| author_facet | Riis, Søren |
| contents | 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}}(Γ,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}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16265 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies Riis, Søren Combinatorics 68Q17 (primary), 05C85, 94A24, 03C13 (secondary) F.1.3; G.2.2; E.4 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}}(Γ,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}. |
| title | Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies |
| topic | Combinatorics 68Q17 (primary), 05C85, 94A24, 03C13 (secondary) F.1.3; G.2.2; E.4 |
| url | https://arxiv.org/abs/2504.16265 |