We investigate excluded minor characterizations of two fundamental classes of matroids: orientable matroids and representable matroids. We prove (i) for any fixed field F, there exist infinitely many excluded minors of rank 3 for the union of the class of orientable matroids and the class of F-representable matroids, and (ii) for any fixed field F with characteristic 0, there exist infinitely many orientable excluded minors of rank 3 for intersection of the class of orientable matroids and the class of F-representable matroids. We show these statements by explicitly constructing infinite families of excluded minors.

Computing the partition function of the Ising model on a graph has been investigated from both sides of computer science and statistical physics, with producing fertile results of P cases, FPTAS/FPRAS cases, inapproximability and intractability. Recently, measurement-based quantum computing as well as quantum annealing open up another bridge between two fields by relating a tree tensor network representing a quantum graph state to a rank decomposition of the graph. This paper makes this bridge wider in both directions. An $O^*(2^{ rac{omega}{2} bw(G)})$-time algorithm is developed for the partition function on n-vertex graph G with branch decomposition of width bw(G), where O* ignores a polynomial factor in n and ω is the matrix multiplication parameter less than 2.37287. Related algorithms of $O^*(4^{rw( ilde{G})})$ time for the tree tensor network are given which are of interest in quantum computation, given rank decomposition of a subdivided graph $ ilde{G}$ with width $rw( ilde{G})$. These algorithms are parameter-exponential, i.e., O*(cp) for constant c and parameter p, and such an algorithm is not known for a more general case of computing the Tutte polynomial in terms of bw(G) (the current best time is O*(min{2n, bw(G)O(bw(G))})) with a negative result in terms of the clique-width, related to the rank-width, under ETH.

Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).

While the graph minor theorem by Robertson and Seymour assures that any minor-closed class of graphs can be characterized by a finite list of excluded minors, such a succinct characterization by excluded minors is not always possible in matroids which are combinatorial abstraction from graphs. The class of matroids representable over a given infinite field is known to have an infinite number of excluded minors. In this paper, we show that, for any algebraic element x over the rational field ℚ the degree of whose minimal polynomial is 2, there exist infinitely many ℚ[x]-representable excluded minors of rank 3 for ℚ-representability. This implies that the knowledge that a given matroid is F-representable where F is a larger field than ℚ does not decrease the difficulty of excluded minors' characterization of ℚ-representability.