Teaching dimension

Let class [math]\displaystyle{ {\mathcal C} }[/math] be sampled as follows: for each [math]\displaystyle{ f\in{X\choose k} }[/math], the concept [math]\displaystyle{ f }[/math] is included in [math]\displaystyle{ {\mathcal C} }[/math] independently with probability [math]\displaystyle{ p }[/math]. The class [math]\displaystyle{ {\mathcal C} }[/math] is in fact an Erdős–Rényi random [math]\displaystyle{ k }[/math]-uniform hypergraph.

Now we try to upper bound the teaching dimension of [math]\displaystyle{ {\mathcal C} }[/math], i.e. to upper bound the probability of the event [math]\displaystyle{ \tau({\mathcal C})\gt t }[/math] for some threshold [math]\displaystyle{ t }[/math]. First, due to union bound,

[math]\displaystyle{ \begin{align} \Pr[\tau({\mathcal C})\gt t] &= \Pr[\exists f\in{\mathcal C}, \tau(f)\gt t]\\ &= \Pr\left[\exists f\in{X\choose k}, f\in{\mathcal C} \wedge \tau(f)\gt t\right]\\ &\le {n\choose k}\Pr[f\in{\mathcal C} \wedge \tau(f)\gt t]\\ &= {n\choose k}\Pr[f\in{\mathcal C}]\cdot\Pr[\tau(f)\gt t\mid f\in{\mathcal C}]\\ &= p{n\choose k} \Pr[\tau(f)\gt t\mid f\in{\mathcal C}]. \end{align} }[/math]

Fix a particular [math]\displaystyle{ f\in{\mathcal C} }[/math], the event that [math]\displaystyle{ \tau(f)\gt t }[/math] is equivalent to that [math]\displaystyle{ \forall S\in{X\choose t}, \exists h\in{\mathcal C}\mbox{ that }h\neq f, (h\triangle f)\cap S=\emptyset }[/math]. For every [math]\displaystyle{ S\in{X\choose t} }[/math], let [math]\displaystyle{ X_S }[/math] be the boolean variable indicating that [math]\displaystyle{ S }[/math] is a teaching set of [math]\displaystyle{ f }[/math], i.e. [math]\displaystyle{ \forall h\in{\mathcal C} }[/math] that [math]\displaystyle{ h\neq f }[/math] it holds that [math]\displaystyle{ (h\triangle f)\cap S\neq \emptyset }[/math].

And let

[math]\displaystyle{ X=\sum_{S\in{X\choose t}}X_S }[/math].

Then

[math]\displaystyle{ \Pr[\tau(f)\gt t] =\Pr[X=0] }[/math]

which due to the Chebyshev's inequality, is bounded as

[math]\displaystyle{ \Pr[X=0] \le \Pr\left[|X-\mathbf{E}[X]|\ge \mathbf{E}[X]\right]\le \frac{\mathbf{Var}[X]}{\mathbf{E}[X]^2}=\frac{\mathbf{E}[X^2]-\mathbf{E}[X]^2}{\mathbf{E}[X]^2}. }[/math]