Name
Abstract | ||
|---|---|---|
We develop a Tutte decomposition theory for matrices and their combinatorial abstractions, bimatroids. As in the graph or matroid case, this theory is based on a deletion-contraction decomposition. The contribution from the deletion, derived by an inclusion-exclusion argument, consists of three terms. With one more term contributed from the contraction, the decomposition has four terms in general. There are universal decomposition invariants, one of them being a corank-nullity polynomial. Under a simple change of variables, the corank-nullity polynomial equals a weighted characteristic polynomial. This gives an analog of an identity of Tutte. Applications to counting and critical problems on matrices and graphs are given. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.jctb.2005.06.009 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
simple change,corank-nullity polynomial,critical problem,tutte polynomial,matrix,universal decomposition invariants,matroid,tutte decomposition theory,weighted characteristic polynomial,bimatroid,matroid case,combinatorial abstraction,inclusion-exclusion argument,deletion-contraction decomposition,characteristic polynomial | Matroid,Tutte 12-cage,Characteristic polynomial,Discrete mathematics,Combinatorics,Tutte polynomial,Tutte theorem,Matrix polynomial,Chromatic polynomial,Mathematics,Tutte matrix | Journal |
Volume | Issue | ISSN |
96 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joseph P. S. Kung | 1 | 78 | 20.60 |