Interpretations of the Tutte and characteristic polynomials of matroids

被引:6
作者
Kochol, Martin [1 ]
机构
[1] MU SAV, Bratislava, Slovakia
关键词
Tutte polynomial; Characteristic polynomial; Matroid; (M; <)-compatible set; COMPUTATIONAL-COMPLEXITY;
D O I
10.1007/s10801-019-00914-6
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We study interpretations of the Tutte and characteristic polynomials of matroids. If M is a matroid with rank function r whose ground set E is given with a linear ordering <, then X. E is called ( M,<)-compatible if X n C = {min(C)} for each circuit C of M. We show that the Tutte polynomial of M equals xr ( M/ X) yr * ( M|X) where X runs through the subsets of E such that X and E\ X are (M*,<)- and ( M,<)-compatible, respectively. Similarly, the characteristic polynomial of M equals (-1)| X| (k - 1)r ( M/ X) where X runs either through ( M *,<)-compatible subsets of E, or through the independent sets of M such that X and E\ X are ( M *,<)- and ( M,<)-compatible, respectively.
引用
收藏
页码:1 / 9
页数:9
相关论文
共 27 条
[1]  
Aigner Martin., 1987, Combinatorial Geometries, V29, P139
[2]   THE COMPLEXITIES OF THE COEFFICIENTS OF THE TUTTE POLYNOMIAL [J].
ANNAN, JD .
DISCRETE APPLIED MATHEMATICS, 1995, 57 (2-3) :93-103
[3]  
[Anonymous], 2011, Matroid Theory
[4]  
[Anonymous], 1993, London Mathematical Society Lecture Note Series, DOI [10.1017/cbo9780511752506, DOI 10.1017/CBO9780511752506]
[5]  
Brylawski T, 2010, MATROID THEORY ITS A, P126
[6]  
Brylawski Thomas, 1992, MATROID APPL, V40, P123
[7]  
Crapo Henry H., 1969, AEQUATIONES MATH, V3, P211, DOI [10.1007/bf01817442, DOI 10.1007/BF01817442]
[8]  
Ellis-Monaghan J, 2020, HDB TUTTE POLYNOMIAL
[9]  
Ellis-Monaghan JA, 2011, STRUCTURAL ANALYSIS OF COMPLEX NETWORKS, P219, DOI 10.1007/978-0-8176-4789-6_9
[10]   External and internal elements of a matroid basis [J].
Etienne, G ;
Las Vergnas, M .
DISCRETE MATHEMATICS, 1998, 179 (1-3) :111-119