I am facing a combinatorial problem where I am interested in the minimum number of constraints of a certain type that uniquely determine a solution. I realize that my problem is highly specific (and I don't really know how to describe it using words, otherwise I'd have chosen a better title), but any pointers to literature on this kind of problems (or related forms) would very much be appreciated. Or, maybe someone directly has a good idea for a solution :)
My search space is, for $n, k \in \mathbb{N}$, the set $S = \{f \colon \{0, \ldots, n-1\} \times \{1, \ldots, k\} \to \{0, \ldots, n-1\}\ |\ \forall 0 \leq i < n, 1 \leq j \leq k: f(i, j) \leq i\}$.
For some $f \colon \{0, \ldots, n-1\} \times \{1, \ldots, k\} \to \{0, \ldots, n-1\}$, define $g \colon \{0, ..., n\} \times \{1, \ldots, k\} \times \{1, \ldots, n\} \to \{0, \ldots, n\}$ as $g(n, j, l) = l$ for all $1 \leq j \leq k, 0 \leq l < n$, and $g(i, j, l) = (f(i, j) + l) \operatorname{mod} (n+1)$ otherwise.
Question: What is the minimal required number of constraints of form $g(\ldots g(g(i, j_1, l_1), j_2, l_2)\ldots, j_m, l_m) \neq n$ such that the constraint system admits a unique solution?
We can obtain an upper bound by limiting ourselves to constraints of form $g(i, j, l) \neq n$ (note that, since $0 \leq f(i, j) \leq i$, reasonable values for $l$ range from $n - i$ to $n$ (inclusive)). For any "true" solution $\hat{f}$, the constraint system
$\forall 1 \leq i < n: \forall 1 \leq j \leq k: \forall n - i \leq l \leq n, l \neq n - \hat{f}(i, j): g(i, j, l) \neq n$
uniquely defines $\hat{f}$, but admits multiple solutions if any constraint is removed. The number of constraints is exactly (note that $l$ ranges over $i$ possible values) $k \cdot \sum\limits_{i=1}^{n-1} i = \frac{kn(n-1)}{2}$.
I am interested in whether this bound is tight, or if constraints of the general type (with nested applications of $g$) can reduce it?
I suspect the former, and could imagine two possible, rather straightforward ways of proving tightness:
1) Given an arbitrary current subset of the search space $S' \subseteq S$, for any constraint of the general form, show that there is a constraint of the restricted form such that the resulting search space is pruned by at least the same amount.
2) Define a valuation function $v \colon 2^S \to \mathbb{R}$ for subsets of the search space such that $v(S) = kn(n-1)/2$, $v(S') > 0$ implies $|S'| > 1$. Then, show that for any subset $S' \subseteq S$ and any single constraint (regardless of the form) resulting in a reduced search space $S'' \subseteq S'$, $v(S') - v(S'') \leq 1$.
However, in both cases I still haven't figured out how to proceed...