Average independence polynomials

The independence polynomial of a graph G is the function i (G, x) = Sigma(kgreater than or equal to0)i(k)x(k), where i(k) is the number of independent sets of vertices in G of cardinality k. We investigate here the average independence polynomial, where the average is taken over all independence polynomials of (labeled) graphs of order n. We prove that while almost every independence polynomial has a nonreal root, the average independence polynomials always have all real, simple roots. (C) 2004 Elsevier Inc. All rights reserved.