| [home] - [up] |
Abstract: The reliability polynomial of a graph G is the function R_G(p) giving the probability that the graph is connected if each edge is operational with independent probability p. If G is connected, and has e edges, then R_G(p) is a polynomial of degree e. In 1992, Jason Brown and Charlie Colbourn conjectured that the complex zeros of the reliability polynomial of a graph lie in the closed disk |p-1|<=1. The Brown-Colbourn conjecture was eventually proved to hold for series-parallel graphs - a very restricted class of graphs. Motivated by applications from statistical physics, Alan Sokal proposed studying the natural multivariate generalization of the reliability polynomial (with one variable for each edge) and in this context proved that (the natural generalization of) the Brown-Colbourn conjecture was also true for series-parallel graphs. However, using a computer, a search for counterexamples to the multivariate version of the Brown-Colbourn conjecture was successful. Sokal and I then used this counterexample to produce counterexamples (with several thousand vertices) to the univariate Brown-Colbourn conjecture. In addition, the greater freedom provided by working in the multivariate context allowed us to completely characterize those graphs satisfying the multivariate Brown-Colbourn conjecture.
If time permits, I will also describe our current work in extending these results to matroids, and outline the open problems that remain to be solved for a complete resolution of this question.
Colloquium - 16:00
Abstract: In this talk, I would like to provide some insights into my 2003-habilitation thesis dealing with algebraic methods in computational geometry.
We start from visibility computations with moving viewpoints in 3-space, which naturally arise e.g. in the visualization of crystalline structures. These algorithmic questions lead to fundamental problems of (real) algebraic geometry concerning the lines simultaneously tangent to given bodies. In the talk, we discuss these problems for the case that the set of admissible bodies consists of balls and polytopes.