q AMS Weekly Seminar | Assistant Professor Ewan Davies | Department of Applied Mathematics and Statistics
When: Sep 21 2023 @ 1:30 PM
Where: Gilman 132
3400 North Charles st
Baltimore, MD 21218

Location: Gilman 132

When: September 21st at 1:30 p.m.

Title: Counting independent sets in dense bipartite graphs

Abstract: Originating in physics, counting independent sets is one of the most studied problems in approximate counting and related fields. While it is hard in general, restricted to bipartite graphs the problem is fascinating and its complexity remains unknown. We will motivate counting independent sets and describe a few recent results that give a polynomial-time algorithm on dense, regular bipartite graphs. The methods we use are interesting in their own right, including graph containers and subspace enumeration.

Bio: Dr. Ewan Davies is an assistant professor in the Department of Computer Science at Colorado State University. He studied mathematics at the University of Cambridge and the London School of Economics and Political Science, and his research interests include algorithms, extremal graph theory and statistical physics. He studies high-dimensional combinatorial spaces and uses intuition from physics and graph theory to design efficient approximation algorithms.

Zoom link: https://wse.zoom.us/j/94601022340