Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Combinatorial problems arising from Horn formulas

Special Events

Speaker: Despina Stasi, Illinois Institute of Technology
Location: 3106 MSB
Start time: Mon, Feb 24 2014, 3:10PM

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.