Gyorgy Turan : Directed hypergraphs and Horn formulas

Posted by Shmuel Friedland , part of the Departmental Colloquium.

At

March 11, 2016, 3 p.m.

In

SEO 636

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