Increasing spanning forests in graphs and simplicial complexes

DOI10.1016/J.EJC.2018.09.011MaRDI QIDQ1633617zbMATH OpenOpenAlexFDO

Authors Jeremy L. Martin, Bruce E. Sagan, Joshua Hallam

Publication date 20 December 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

generating functionchromatic polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Combinatorial aspects of simplicial complexes (05E45)

Abstract: Let G be a graph with vertex set {1,...,n}. A spanning forest F of G is increasing if the sequence of labels on any path starting at the minimum vertex of a tree of F form an increasing sequence. Hallam and Sagan showed that the generating function ISF(G,t) for increasing spanning forests of G has all nonpositive integral roots. Furthermore they proved that, up to a change of sign, this polynomial equals the chromatic polynomial of G precisely when 1,...,n is a perfect elimination order for G. We give new, purely combinatorial proofs of these results which permit us to generalize them in several ways. For example, we are able to bound the coefficients of ISF(G,t) using broken circuits. We are also able to extend these results to simplicial complexes using the new notion of a cage-free complex. A generalization to labeled multigraphs is also given. We end by exploring spanning forests where the increasing condition is replaced by having the label sequences avoid the patterns 231, 312, and 321.

Recommendations

• A local injective proof of log-concavity for increasing spanning forests
• A partition of connected graphs
• A symmetric function of increasing forests
• Determinantal generating functions of colored spanning forests
• Chromatic polynomials and order ideals of monomials

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• A class of hypergraphs that generalizes chordal graphs
• A logical expansion in mathematics
• Acyclic orientations of graphs
• An introduction to hyperplane arrangements
• Bijective proofs of two broken circuit theorems
• Chordal and sequentially Cohen-Macaulay clutters
• Combinatorics and commutative algebra.
• Combinatorics and topology of complements of hyperplanes
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Factoring the characteristic polynomial of a lattice
• Higher chordality: from graphs to complexes
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Permutation patterns and statistics
• Signed graph coloring
• Simplicial and cellular trees
• Supersolvable lattices

Cited in

(8)

• Increasing forests and quadrangulations via a bijective approach
• Whitney duals of geometric lattices
• The noncrossing bond poset of a graph
• The amazing chromatic polynomial
• A local injective proof of log-concavity for increasing spanning forests
• The Whitney duals of a graded poset
• The noncrossing bond poset of a graph
• Spanning forests of a digraph and their applications

This page was built for publication: Increasing spanning forests in graphs and simplicial complexes

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