Ten years of work on the Brown-Colbourn conjecture

David Wagner

University of Waterloo

November 22,
refreshments at 3:45pm


The reliability polynomial $R(G;q)$ of a (finite, connected, loopless, multi-) graph is the probability that if each edge is deleted independently with probability $q$, then the remaining spanning subgraph is still connected. In 1992, Brown and Colbourn conjectured that every complex zero of the polynomial $R(G;q)$ lies in the closed unit disc $|q|\leq 1$. In this talk I will review the progress which has been made towards understanding this conjecture over the past decade, including work of Brown, Colbourn, Sokal, Chari, Choe, Royle, and others. Possible generalizations to matroids, and implications for the $f$--vectors of matroids will also be discussed.

Speaker's Contact Info: dgwagner(at-sign)pythagoras.math.uwaterloo.ca

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on October 25, 2002 at 01:32 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.