skip to content

Dominant traits in the zeros of two-variate two-terminal reliability polynomials

Friday 25th January 2008 - 14:00 to 14:30
INI Seminar Room 1

Various polynomials appear in graph theory: chromatic polynomials, flow polynomials, all-terminal reliability polynomials. All these polynomials are special instances of the Tutte polynomial, and the location of their complex zeros has been actively studied (Biggs, Brown & Colbourn, Chang & Shrock, Royle, Sokal, Welsh, to name but a few). General results have been established for the zeros of recursively defined families of polynomials (Beraha, Kahane, and Weiss): the zeros aggregate asymptotically to sets of algebraic curves and sometimes to isolated points.

In this contribution, we address the two-terminal (or end-to-end) reliability polynomial Rel2, which corresponds to the connectivity of two sites of a graph. Admittedly, this is no graph invariant. However, instead of using the variable $p$ for the (uniform) probability for correct operation of the edges of the graph, we may now consider two variables $p$ and $\rho$ for the edge and site reliabilities, respectively. For a given graph and a pair of sites, we can study the location of the complex zeros of Rel2($p$,$\rho$) as a function of $\rho$.

We present results on a few recursive families of graphs for which the two-terminal reliability polynomial may be computed exactly as a function of $p$,$\rho$ and $n$ (the size of the graph); the associated generating functions have also been derived. The asymptotic (for $n$ going to infinity) location of zeros has been investigated and exhibits:

- the usual sets of algebraic curves,

- appearing (or disappearing) sets of isolated zeros in some cases,

- an expansion of the general structure as $\rho$ goes to 0, which can be described by a power law.

The set of zeros also undergoes several structural transitions at specific, critical values $\rho_c$ --- which are algebraic --- as $\rho$ decreases from 1 to 0.

More surprisingly, by slightly changing the building blocks of the recursive graphs, we may also numerically observe:

- particular values of $\rho$ for which the sets of zeros look much smoother,

- existence (or not!) of several prevailing sets of isolated zeros with different symmetries (of orders 3 and 13, for instance),

- different ``exploding'' families of algebraic curves with different symmetries and expansion rates, too.

Asymptotic, analytical expressions for the above phenomena can actually be deduced from the generating function.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons