×

A MacWilliams type identity for matroids. (English) Zbl 1145.94014

Summary: We consider the coboundary polynomial for a matroid as a generalization of the weight enumerator of a linear code. By describing properties of this polynomial and of a more general polynomial, we investigate the matroid analogue of the MacWilliams identity. From coding-theoretical approaches, upper bounds are given on the size of circuits and cocircuits of a matroid, which generalizes bounds on minimum Hamming weights of linear codes due to I. Duursma [Discrete Math. 268, No. 1–3, 103–127 (2003; Zbl 1039.94015)].

MSC:

94B05 Linear codes (general theory)
05B35 Combinatorial aspects of matroids and geometric lattices

Citations:

Zbl 1039.94015
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] T. Britz, MacWilliams identities and matroid polynomials, Electron. J. Combin. 9 (Research paper R19) (2002) 17.; T. Britz, MacWilliams identities and matroid polynomials, Electron. J. Combin. 9 (Research paper R19) (2002) 17. · Zbl 1038.05008
[2] Britz, T., Extensions of the critical theorem, Discrete Math., 305, 55-73 (2005) · Zbl 1092.94029
[3] Brylawski, T., Intersection theory for embeddings of matroids into uniform geometries, Stud. Appl. Math., 61, 211-244 (1979) · Zbl 0478.05022
[4] Brylawski, T.; Oxley, J., The Tutte polynomial and its applications, (White, N., Matroid Applications (1992), Cambridge University Press: Cambridge University Press Cambridge, New York), 123-225 · Zbl 0769.05026
[5] P.J. Cameron, Cycle index, weight enumerator, and Tutte polynomial, Electron. J. Combin. 9 (Note 2) (2002) 10.; P.J. Cameron, Cycle index, weight enumerator, and Tutte polynomial, Electron. J. Combin. 9 (Note 2) (2002) 10. · Zbl 0985.05001
[6] Crapo, H., The Tutte polynomial, Aequationes Math., 3, 211-229 (1969) · Zbl 0197.50202
[7] Crapo, H. H., Möbius inversion in lattices, Arch. Math., 19, 595-607 (1969) · Zbl 0208.29303
[8] Crapo, H.; Rota, G.-C., On the foundations of combinatorial theory: Combinatorial geometries (Preliminary edition) (1970), The MIT Press: The MIT Press Cambridge, MA, London · Zbl 0216.02101
[9] Duursma, I., Extremal weight enumerators and ultraspherical polynomials, Discrete Math., 268, 103-127 (2003) · Zbl 1039.94015
[10] Fortuin, C. M.; Kastelyn, P. W., On the random-cluster model, I: Introduction and relation to other models, Physica: Introduction and relation to other models, 57, 536-564 (1972)
[11] Gordon, G.; Traldi, L., Generalized activities and the Tutte polynomial, Discrete Math., 85, 167-176 (1990) · Zbl 0742.05022
[12] MacWilliams, F. J., A theorem on the distribution of weights in a systematic code, Bell System Tech. J., 42, 79-94 (1963)
[13] MacWilliams, F. J.; Sloane, N. J., The Theory of Error-Correcting Codes (1978), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam · Zbl 0369.94008
[14] Mphako, E. G., Tutte polynomials of perfect matroid designs, Combin. Probab. Comput., 9, 363-367 (2000) · Zbl 0964.05017
[15] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[16] Read, R. C.; Whitehead, E. G., The Tutte polynomial for homeo-morphism classes of graphs, Discrete Math., 243, 267-272 (2002) · Zbl 0998.05022
[17] Shiromoto, K., A new MacWilliams type identity for linear codes, Hokkaido Math. J., 25, 651-656 (1996) · Zbl 0868.05006
[18] Sokal, A. D., Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions, Combin. Probab. Comput., 10, 41-77 (2001) · Zbl 0999.82022
[19] Traldi, L., A dichromatic polynomial for weighted graphs and link polynomials, Proc. Amer. Math. Soc., 106, 279-287 (1989) · Zbl 0713.57003
[20] Traldi, L., Chain polynomials and Tutte polynomials, Discrete Math., 248, 279-282 (2002) · Zbl 0997.05038
[21] Tutte, W. T., Lectures on matroids, J. Res. Natl. Bur. Stand., Sect. B, 69, 1-47 (1965) · Zbl 0151.33801
[22] van Lint, J. H., Introduction to Coding Theory (1999), Springer: Springer Berlin · Zbl 0936.94014
[23] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002
[24] Welsh, D. J.A.; Whittle, G. P., Arrangements, channel assignments, and associated polynomials, Adv. Appl. Math., 23, 375-406 (1999) · Zbl 0942.05063
[25] Whitney, H., On the abstract properties of linear dependence, Amer. J. Math., 57, 509-533 (1935) · JFM 61.0073.03
[26] Whittle, G. P., Characteristic polynomials of weighted lattices, Adv. Math., 99, 125-151 (1993) · Zbl 0787.05024
[27] Zaslavsky, T., Strong Tutte functions of matroids and graphs, Trans. Amer. Math. Soc., 334, 317-347 (1992) · Zbl 0781.05012
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.