Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Horn formulas are an important fragment of propositional logic, with various applications including knowledge representation and reasoning. We discuss the correspondence between definite Horn formulas and directed hypergraphs and some combinatorial problems that it produces. As our first problem we consider the property that in a random 3-uniform directed hypergraph there is a pair of vertices for which a forward-chaining type markings process marks all vertices. We then define and study the hydra number of a graph, a graph invariant that arises from a combinatorial reformulation of a restricted version of the NP-hard problem of Horn formula minimization. This talk is based on joint work with Robert H. Sloan and Gyorgy Turan.