Department of Mathematics, University of Washington - Combinatorics and Geometry Seminar, Dept. of Mathematics
Acyclic digraphs are used to represent the underlying relationships of some Bayesian belief networks, which are in turn used in expert systems and other representations of statistically interdependent items. But the set of such digraphs turns out to be too big and, instead, a smaller number of equivalence classes truly represent the set of possible networks. Until now, little has been known about the combinatorial properties of these classes, such as their asymptotic growth with number of vertices or the average class size. This discussion will cover recent computer investigations into the classes and, time permitting, some of the mathematics involved in making possible a computer analysis of a quadrillion digraphs (in a single night!). No prior knowledge of the topic will be required.
This is joint work with Michael Perlman of Statistics.