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. We denote that [math]\displaystyle{ m=p{n\choose k} }[/math], which is the expected size of [math]\displaystyle{ {\mathcal C} }[/math].

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}]\\ &= m \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}=\frac{\mathbf{E}[X^2]}{\mathbf{E}[X]^2}-1. }[/math]

We then hope that [math]\displaystyle{ \mathbf{E}[X^2]=\left(1+o\left(m^{-1}\right)\right)\mathbf{E}[X]^2 }[/math].

[math]\displaystyle{ \begin{align} \mathbf{E}[X^2] &= \mathbf{E}\left[\left(\sum_{S\in{X\choose t}}X_S\right)^2\right]\\ &= \mathbf{E}\left[\sum_{S\in{X\choose t}}X_S^2+\sum_{S,T\in{X\choose t}\atop S\neq T}X_SX_T\right]\\ &= \mathbf{E}\left[\sum_{S\in{X\choose t}}X_S\right]+\sum_{S,T\in{X\choose t}\atop S\neq T}\mathbf{E}\left[X_SX_T\right]\\ &= \mathbf{E}\left[X\right]+\sum_{S,T\in{X\choose t}\atop S\neq T}\Pr\left[\mbox{both }S\mbox{ and }T\mbox{ are teaching sets of }f\right]. \end{align} }[/math]

Then compute [math]\displaystyle{ \mathbf{E}[X] }[/math] and the above probability.