Consider an "ambiguous" function class
$F^\star\subseteq\{0,1,\star\}^X$ (i.e., $F$ consists of Boolean functions acting on a set $X$ with some missing values, indicated by $\star$).
We say that
$F^\star$ *shatters* a set $S\subseteq X$
if $F^\star(S)\supseteq\{0,1\}^S$.
Define $VC(F^\star)$ as the maximal size of any shattered set (possibly, $\infty$).


We say that $\bar f\in\{0,1\}^X$ is a *disambiguation*
of $f^\star\in F^\star$ if
the two functions agree on $x\in X$
whenever $f^\star(x)\neq\star$.
We say that $\bar F\subseteq\{0,1\}^X$ is a disambiguation of
$F^\star$ if each $\bar f\in \bar F$
is a disambiguation of
*some* $f^\star\in F^\star$
and *every* $f^\star\in F^\star$
has a disambiguated representative $\bar f\in \bar F$.


Conjecture: There is a universal constant $c$ such that for any ambiguous
$F^\star$ there is a disambiguation $\bar F$ such that
$$ 
VC(\bar F)
\le c 
VC(F^\star) 
.$$


Note:
This open problem was posed here:
<https://arxiv.org/abs/1810.02180> .
It is known that $c$ must be $>1$, and Lemma 6.2 therein provides an analog of Sauer's lemma for $F^\star$.



VC-dimension of disambiguated classes
This has been disproved in Theorem 11 of [Alon, Hanneke, Holzman, and Moran](https://arxiv.org/abs/2107.08444). The proof is short and elegant (building on recent deep results of others').


