  The problem of learning Markov equivalence classes of Bayesian network
structures may be solved by searching for the maximum of a scoring metric in a
space of these classes. This paper deals with the definition and analysis of
one such search space. We use a theoretically motivated neighbourhood, the
inclusion boundary, and represent equivalence classes by essential graphs. We
show that this search space is connected and that the score of the neighbours
can be evaluated incrementally. We devise a practical way of building this
neighbourhood for an essential graph that is purely graphical and does not
explicitely refer to the underlying independences. We find that its size can be
intractable, depending on the complexity of the essential graph of the
equivalence class. The emphasis is put on the potential use of this space with
greedy hill -climbing search
