Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-29T16:01:51.849Z Has data issue: false hasContentIssue false
  • English
  • Français

Some Inequalities for Whitney–Tutte Polynomials

Published online by Cambridge University Press:  11 December 2009

ARUN P. MANI
ARUN P. MANI*
Affiliation:
Clayton School of Information Technology, Monash University, Clayton VIC 3800, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce and prove a family of inequalities satisfied by the Whitney rank generating function of a matroid in the positive quadrant of ℝ2. These can be interpreted as correlation inequalities at those points where the polynomial is known to count the number of independent sets, bases or spanning sets of the matroid. Our proofs also introduce an idea of rank dominating bijections in matroids, which are then used to obtain some simple extensions of the submodular property of matroid ranks.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 3 , May 2010 , pp. 425 - 439
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Cocks, C. C. (2008) Correlated matroids. Combin. Probab. Comput. 17 511–518.CrossRefGoogle Scholar
[2]Feder, T. and Mihail, M. (1992) Balanced matroids. In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, pp. 26–38.Google Scholar
[3]Goldberg, L. A. and Jerrum, M. (2008) Inapproximability of the Tutte polynomial. Inform. Comput. 206 908–929.CrossRefGoogle Scholar
[4]Grimmett, G. R. and Winkler, S. N. (2004) Negative association in uniform forests and connected graphs. Random Struct. Alg. 24 444–460.CrossRefGoogle Scholar
[5]Jaeger, F., Vertigan, D. L. and Welsh, D. J. A. (1990) On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Phil. Soc. 108 35–53.CrossRefGoogle Scholar
[6]Mani, A. P. An extension to matroid rank submodularity and the Z-Rayleigh property. In preparation.Google Scholar
[7]Noble, S. (2008) Private communication.Google Scholar
[8]Oxley, J. G. (1992) Matroid Theory, Oxford University Press.Google Scholar
[9]Semple, C. and Welsh, D. J. A. (2008) Negative correlation in graphs and matroids. Combin. Probab. Comput. 17 423–435.CrossRefGoogle Scholar
[10]Seymour, P. and Welsh, D. J. A. (1975) Combinatorial applications of an inequality from statistical mechanics. Math. Proc. Cambridge Phil. Soc. 77 485–495.CrossRefGoogle Scholar