Abstract

A matching in a graph is a collection of edges no two of which share a vertex. An independent set is a collection of vertices no two of which are spanned by an edge. Both matchings and independent sets arise as configurations in well-studied studied statistical physics models, namely the dimer model and the hard-core model. A theorem of Bregman implies that among all $d$-regular, $N$-vertex bipartite graphs, the one with the most matchings of size $N/2$ (the maximum possible size) is the graph $K(N,d)$ composed of the disjoint union of $N/2d$ complete $d$-regular bipartite graphs. Recently Friedland has conjectured that among $d$-regular, $N$-vertex bipartite graphs, $K(N,d)$ admits the most matchings of size $k$ for any $0 \leq k \leq N/2$. In this talk we report on work in progress using methods from information theory to provide asymptotic evidence for Friedland's conjecture, and its natural analog for independent sets.

Joint work with Teena Carroll (Norbert College) and Prasad Tetali (Georgia Tech).

THURSDAY, December 4, 2008
Time: 4:30 P.M.
Location: WeH 5320