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} (E, 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}.

Questo articolo esplora i giri e le loro implicazioni.

Scarica PDF: