Departmental Colloquium
Gyorgy Turan
UIC
Directed hypergraphs and Horn formulas
Abstract: A directed hypergraph has edges of the form a,b --> c, i.e., edges
have a single head, but can have multiple vertices in the tail. This is a
generalization of directed graphs. Directed hypergraphs are closely
related to Horn formulas in logic, closure operators, lattices and
functional dependencies in databases.
The study of these concepts is an area where `graph theory meets reasoning'.
We discuss directed hypergraphs from the point of view of optimization,
extremal and probabilistic combinatorics, and knowledge representation
and reasoning in artificial intelligence.
4:15 PM in 300 SEO
Friday March 11, 2016 at 3:00 PM in SEO 636