A version of Tutte's polynomial for hypergraphs

DOI10.1016/J.AIM.2013.06.001zbMATH Open1283.05136arXiv1103.1057OpenAlexW2964309663MaRDI QIDQ2437429FDOQ2437429

Authors: Tamás Kálmán 

Publication date: 3 March 2014

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

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.

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

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

zbMATH Keywords

bipartite graphhypergraphTutte polynomialplanar dualityinteger polytopearborescence number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A Contribution to the Theory of Chromatic Polynomials
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph polynomials and their applications. I: The Tutte polynomial
• Permutohedra, Associahedra, and Beyond
• A Proof of Tuite’s Trinity Theorem and a New Determinant Formula
• Title not available (Why is that?)
• A new invariant of plane bipartite cubic graphs
• Title not available (Why is that?)

Cited In (22)

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

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)