5 research outputs found
A decomposition theorem for the linking polynomial of two matroids
No full textAbstractIn [W. Kook, V. Reiner, D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B 76 (1999) 297–300], it is proved that the Tutte polynomial of a matroid can be decomposed into a colouring factor and a flow factor as follows:T(M;x,y)=∑X⊆ET(M|X;0,y)T(M/X;x,0).We extend this decomposition to the linking polynomial of two matroids defined in [D.J.A. Welsh, K.K. Kayibi, A linking polynomial of two matroids, Adv. in Appl. Math. 32 (2004) 391–419]
T-tetrominoes tiling's Markov chain mixes fast
No full textKorn and Pak (2007) [3] conjectured that there exists a fully polynomial randomized approximation scheme (fpras) for approximating the number of ways of tiling a 4n x 4m rectangular lattice with T-tetrominoes. Using a flow argument, we prove this conjecture in affirmative by showing that the mixing time of an appropriate Markov chain is polynomial in the area of the lattice. - 2017 Elsevier B.V.The authors thank the anonymous referees for their valuable comments and suggestions. We would like to thank Qatar University, Doha, Qatar, and University of Hull, UK, and University of Kashmir, Srinagar, India for providing facilities and support during the preparation of the final form of this paper. The research of second author is supported by SERB-DST , New Delhi under the research project number EMR/2015/001047/MS .Scopu
On some extensions of the Tutte polynomial
No full textAvailable from British Library Document Supply Centre- DSC:DN063055 / BLDSC - British Library Document Supply CentreSIGLEGBUnited Kingdo
A linking polynomial of two matroids
No full textAbstractWe introduce a 4-variable polynomial Q as a natural invariant linking a pair of matroids on a common ground set. The polynomial Q has similarities with the classical Tutte polynomial of a single matroid, it contains as specialisations the generating function of common independent and spanning sets of a given size, it behaves naturally under a duality transform and there is a recipe theorem which shows that essentially it is the unique invariant satisfying simultaneous delete/contract recursions on a pair of matroids
