The Merino-Welsh conjecture is false for matroids.(English)Zbl 1536.05257
Summary: The matroidal version of the Merino-Welsh conjecture [C. Merino andD. J. A. Welsh, Ann. Comb. 3, No. 2–4, 417–429 (1999;Zbl 0936.05043)] states that the Tutte polynomial \(T_M(x, y)\) of any matroid \(M\) without loops and coloops satisfies that\[\max(T_M(2, 0), T_M(0, 2)) \geqslant T_M(1, 1).\]Equivalently, if the Merino-Welsh conjecture is true for all matroids without loops and coloops, then the following inequalities are also satisfied for all matroids without loops and coloops:\[T_M(2, 0) + T_M(0, 2) \geqslant 2 T_M(1, 1),\]and\[T_M(2, 0) T_M(0, 2) \geqslant T_M (1, 1)^2.\]We show a counter-example for these inequalities.
MSC:
| 05C31 | Graph polynomials |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
Citations:
Zbl 0936.05043Cite
References:
| [1] | Beke, C.; Csáji, G. K.; Csikvári, P.; Pituk, S., Permutation Tutte polynomial, 2023, arxiv preprint |
| [2] | Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (Matroid Applications, vol. 40, 1992), 123-225 ·Zbl 0769.05026 |
| [3] | Chávez-Lomelí, L. E.; Merino, C.; Noble, S. D.; Ramírez-Ibáñez, M., Some inequalities for the Tutte polynomial, Eur. J. Comb., 32, 3, 422-433, 2011 ·Zbl 1290.05055 |
| [4] | Conde, R.; Merino, C., Comparing the number of acyclic and totally cyclic orientations with that of spanning trees of a graph, Int. J. Math. Comput., 2, 79-89, 2009 ·Zbl 1198.05015 |
| [5] | Crapo, H. H., The Tutte polynomial, Aequ. Math., 3, 3, 211-229, 1969 ·Zbl 0197.50202 |
| [6] | Ellis-Monaghan, J. A.; Merino, C., Graph polynomials and their applications I: the Tutte polynomial, (Structural Analysis of Complex Networks, 2011, Springer), 219-255 ·Zbl 1221.05002 |
| [7] | Ellis-Monaghan, J. A.; Moffatt, I., Handbook of the Tutte Polynomial and Related Topics, 2022, CRC Press ·Zbl 1495.05001 |
| [8] | Ferroni, L., Matroids are not Ehrhart positive, Adv. Math., 402, Article 108337 pp., 2022 ·Zbl 1487.52022 |
| [9] | Ferroni, L.; Schröter, B., Valuative invariants for large classes of matroids, 2022, arXiv preprint |
| [10] | Ferroni, L.; Schröter, B., The Merino-Welsh conjecture for split matroids, Ann. Comb., 27, 3, 737-748, 2023 ·Zbl 1526.05027 |
| [11] | Jackson, B., An inequality for Tutte polynomials, Combinatorica, 30, 69-81, 2010 ·Zbl 1225.05135 |
| [12] | Jaeger, F.; Vertigan, D. L.; Welsh, D. J.A., On the Computational Complexity of the Jones and Tutte Polynomials, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 108, 35-53, 1990, Cambridge University Press ·Zbl 0747.57006 |
| [13] | Knauer, K.; Martínez-Sandoval, L.; Luis Ramírez Alfonsín, J., A Tutte polynomial inequality for lattice path matroids, Adv. Appl. Math., 94, 23-38, 2018 ·Zbl 1377.05089 |
| [14] | Kung, J. P.S., Inconsequential results on the Merino-Welsh conjecture for Tutte polynomials, 2021, arXiv preprint |
| [15] | Lin, F., A note on spanning trees and totally cyclic orientations of 3-connected graphs, J. Comb., 4, 1, 95-104, 2013 ·Zbl 1301.05070 |
| [16] | Merino, C.; Ibañez, M.; Rodríguez, G., A note on some inequalities for the Tutte polynomial of a matroid, Electron. Notes Discrete Math., 34, 603-607, 2009 ·Zbl 1273.05032 |
| [17] | Merino, C.; Ramírez-Ibáñez, M.; Rodríguez-Sánchez, G., The Tutte polynomial of some matroids, Int. J. Comb., 2012, 2012 ·Zbl 1267.05145 |
| [18] | Merino, C.; Welsh, D., Forests, colorings and acyclic orientations of the square lattice, Ann. Comb., 3, 2-4, 417-429, 1999 ·Zbl 0936.05043 |
| [19] | Noble, S. D.; Royle, G. F., The Merino-Welsh conjecture holds for series-parallel graphs, Eur. J. Comb., 38, 24-35, 2014 ·Zbl 1282.05031 |
| [20] | Oxley, J., Matroid Theory, 1992, Oxford University Press ·Zbl 0784.05002 |
| [21] | Thomassen, C., Spanning trees and orientations of graphs, J. Comb., 1, 2, 101-111, 2010 ·Zbl 1219.05044 |
| [22] | Tutte, W. T., A contribution to the theory of chromatic polynomials, Can. J. Math., 6, 80-91, 1954 ·Zbl 0055.17101 |
| [23] | Welsh, D., The Tutte polynomial, Random Struct. Algorithms, 15, 3-4, 210-228, 1999 ·Zbl 0934.05057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
