Combinatorics Seminar
When: Sunday, November 8, 10am
Where: Schreiber 309
Speaker: Daniel Marx, Tel Aviv University
Title: Combinatorial problems related to treewidth and its
generalizations to hypergraphs
Abstract:
Treewidth is a graph measure that plays an important role both
in graph theory and in algorithmic applications such as
constraint satisfaction problems. In my talk, I will highlight
some well-known and recent results and problems related to
treewidth. Certain applications in database theory motivated
the study of generalizations of treewidth on hypergraphs. These
questions turned out to be very interesting combinatorially,
with surprising connections to entropy and submodularity.