<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 9 Issue 3" %>
Bounding the Roots of Ideal and Open Set Polynomials
Jason I. Brown1, Carl A. Hickman2, Hugh Thomas3, and David G. Wagner4
1Department of Mathematics and Statistics and Faculty of Computer Science, Dalhousie University, Halifax, Nova Scotia, B3H 3J5, Canada
2The Fields Institute for Research in Mathematical Sciences, Toronto, Ontario, M5T 3J1, Canada
3Department of Mathematics and Statistics, University of New Brunswick, Fredericton, New Brunswick, E3B 5A3, Canada
4Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Annals of Combinatorics 9 (3) p.259-268 September, 2005
AMS Subject Classification: 05A15, 06A11, 12D10, 54A10
Let P be a preorder (i.e. reflexive, transitive relation) on a finite set X. The ideal polynomial of P is the function , where dk is the number of ideals (i.e. downwards closed sets) of cardinality k in P. We provide upper bounds for the moduli of the roots of idealP(x) in terms of the width of P. We also provide examples of preorders with roots of large moduli. The results have direct applications to the generating polynomials counting open sets in finite topologies.
Keywords: preorder, poset, ideal, polynomial, roots, finite topology, open set


1. F. Brenti, G.F. Royle, and D.G. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canad. J. Math. 46 (1994) 55--80.

2. J.I. Brown and C.J. Colbourn, On the log concavity of reliability and matroidal sequences, Adv. Appl. Math. 15 (1994) 114--127.

3. J.I. Brown and C.J. Colbourn, Roots of the reliability polynomial, SIAM J. Discrete Math. 5 (1992) 571--585.

4. J.I. Brown, Chromatic polynomials and order ideals of monomials, Discrete Math. 189 (1998) 43--68.

5. J.I. Brown, K. Dilcher, and R.J. Nowakowski, Roots of independence polynomials of well covered graphs, J. Algebraic Combin. 11 (2000) 197--210.

6. J.I. Brown and R.J. Nowakowski, Bounding the roots of independence polynomials, Ars Combin. 58 (2001) 113--120.

7. J.I. Brown, C.A. Hickman, A.D. Sokal, and D.G. Wagner, On the chromatic roots of generalized theta graphs, J. Combin. Theory Ser. B 83 (2001) 272--297.

8. J.I. Brown and C.A. Hickman, On chromatic roots of large subdivisions of graphs, Discrete Math. 242 (2002) 17--30.

9. J.I. Brown and C.A. Hickman, On chromatic roots with negative real part, Ars Combin. 63 (2002) 211--221.

10. J.I. Brown, C.A. Hickman, and R.J. Nowakowski, On the location of roots of independence polynomials, J. Algebraic Combin. 19 (2004) 273--282.

11. J.I. Brown, C.A. Hickman, and R.J. Nowakowski, The independence fractal of a graph, J. Combin. Theory Ser. B 87 (2003) 209?--230.

12. R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth, On the Lambert W function, Adv. Comput. Math. 5 (1996) 329--359.

13. S.K. Das, A machine representation of finite T0 topologies, J. Assoc. Comput. Mach. 24 (1977) 676--692.

14. M. Erné, Struktur--und Anzahlformeln fur Topologien auf endlichen Mengen, Manuscripta Math. 11 (1974) 221--259.

15. J.W. Evans, F. Harary, and M.S. Lynn, On the computer enumeration of finite topologies, Commun. ACM 10 (1967) 295--297.

16. D.C. Fisher and A.E. Solow, Dependence polynomials, Discrete Math. 82 (1990) 251--258.

17. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.

18. I. Gutman, An identity for the independence polynomials of trees, Publ. Inst. Math. (Belgrade) 50 (1991) 19--23.

19. I. Gutman, Some analytic properties of the independence and matching polynomials, Match. 28 (1992) 139--150.

20. C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 25 (1994) 219--228.

21. B. Jackson, A zero--free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993) 325--336.

22. A.S. Mashhour, M.E. Abd El-Monsef, and A.S. Farrag, Remarks on maximum cardinality for topologies on finite sets, Delta J. Sci. 10 (1986) 496--512.

23. R. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52--71.

24. R.C. Read and G.F. Royle, Chromatic roots of families of graphs, In: Graph Theory, Combinatorics and Applications, Vol. 2,
Y. Alavi, G. Chartrand, O.R. Oellermann, and A.J. Schwenk, Eds., Wiley, New York, (1991) pp. 1009--1029.

25. R.C. Read and W.T. Tutte, Chromatic polynomials, In: Selected Topics in Graph Theory 3, L.W. Beineke and R.J. Wilson, Eds., Academic Press, New York, (1988) pp. 15--42.

26. G. Royle and A.D. Sokal, The Brown-Colbourn conjecture on zeros of reliability polynomials is false, J. Combin. Theory Ser. B 91 (2004) 345--360.

27. A.D. Sokal, Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions, Combin. Probab. Comput. 10 (2001) 41--77.

28. A.D. Sokal, Chromatic roots are dense in the whole complex plane, Combin. Probab. Comput. 13 (2004) 221--261.

29. R.P. Stanley, On the number of open sets of finite topologies, J. Combin. Theory 10 (1971) 74--79.

30. R.P. Stanley, An extremal problem for finite topologies and distributive lattices, J. Combin. Theory Ser. A 14 (1973) 209--214.

31. D. Stephen, Topology on fioite sets, Amer. Math. Monthly 75 (1968) 739--741.

32. V. Thier, Graphen and polynome, Ph. D. Thesis, TU München, 1983.

33. W.T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins, Baltimore, 1992.