A version of Tutte's polynomial for hypergraphs

DOI10.1016/J.AIM.2013.06.001MaRDI QIDQ2437429zbMATH OpenOpenAlexFDO

Authors Tamás Kálmán

Publication date 3 March 2014

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.1057

zbMATH Keywords

bipartite graphhypergraphTutte polynomialplanar dualityinteger polytopearborescence number

Mathematics Subject Classification ID

Graph polynomials (05C31) Hypergraphs (05C65) Polytopes and polyhedra (52B99)

Abstract: Tutte's dichromate T(x,y) is a well known graph invariant. Using the original definition in terms of internal and external activities as our point of departure, we generalize the valuations T(x,1) and T(1,y) to hypergraphs. In the definition, we associate activities to hypertrees, which are generalizations of the indicator function of the edge set of a spanning tree. We prove that hypertrees form a lattice polytope which is the set of bases in a polymatroid. In fact, we extend our invariants to integer polymatroids as well. We also examine hypergraphs that can be represented by planar bipartite graphs, write their hypertree polytopes in the form of a determinant, and prove a duality property that leads to an extension of Tutte's Tree Trinity Theorem.

Recommendations

• Universal Tutte polynomial
• scientific article; zbMATH DE number 475578
• Hypergraph polynomials and the Bernardi process
• A characterization of Tutte invariants of 2-polymatroids
• Multivariable, parameterized, and colored extensions of the Tutte polynomial

Cites work

• scientific article; zbMATH DE number 3482371 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A Proof of Tuite’s Trinity Theorem and a New Determinant Formula
• A new invariant of plane bipartite cubic graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph polynomials and their applications. I: The Tutte polynomial
• Permutohedra, Associahedra, and Beyond

Cited in

(22)

• Spanning hypertrees, vertex tours and meanders
• Binary functions, degeneracy, and alternating dimaps
• The Tutte polynomial via lattice point counting
• Hypergraph polynomials and the Bernardi process
• Symmetric edge polytopes and matching generating polynomials
• Flag matroids: algebra and geometry
• Root polytopes and Jaeger‐type dissections for directed graphs
• Reflexive polytopes arising from bipartite graphs with \(\gamma\)-positivity associated to interior polynomials
• Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
• The interior and exterior polynomials are well-defined
• Universal Tutte polynomial
• PQ-type adjacency polytopes of join graphs
• Interior polynomial for signed bipartite graphs and the HOMFLY polynomial
• Formulas for the computation of the Tutte polynomial of graphs with parallel classes
• Permutation Tutte polynomial
• Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs
• Effective divisor classes on metric graphs
• A Tutte polynomial for signed graphs
• The \(h^\ast\)-polynomials of locally anti-blocking lattice polytopes and their \(\gamma\)-positivity
• Toric rings of perfectly matchable subgraph polytopes
• On \(P\)-unique hypergraphs
• On the polymatroid Tutte polynomial

This page was built for publication: A version of Tutte's polynomial for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437429)