We next review a fundamental result which is a crucial ingredient in the design of our algorithms, namely the one-inclusion hypergraph algorithm \(\mathbb {A}_{\mathcal {H}}\)  for the class \(\mathcal {H}\subseteq [k]^\mathcal {X}\)  [1]}, [2]}, [3]}, [4]}. This algorithm gets as input a training set \((x_1,y_1),...,(x_n,y_n)\)  realizable by \(\mathcal {H}\)  and an additional example \(x\) . The goal is to predict the label of \(x\) . In this sense, the one-inclusion graph constitutes a transductive model in machine learning. The idea is to construct the one-inclusion (hyper)graph of \(\mathcal {H}|_{x_1,...,x_n,x} \subseteq [k]^{n+1}\) . The nodes of this graph are the equivalence classes of \(\mathcal {H}\)  induced by the examples \(x_1,...,x_n,x\) . For the binary classification case, two equivalence classes are connected with an edge if the nodes differ by exactly one element \(x\)  of the \(n+1\)  points and \(x\)  appears only once in \((x_1,...,x_n,x)\) . For the case \(k > 1\) , the hyperedge set is is generalized accordingly. Having created the one-inclusion graph, the goal is to orient the edges; the crucial property is that good orientations of this graph yield low error learning algorithms. Here, an orientation is good if the maximum out-degree of the graph is small. Intuitively, if the maximum out-degree of any node is \(M\) , then this can yield a prediction for the label \(x\)  with \(n+1\)  training samples with permutation mistake bound at most \(M/(n+1)\) .
