Polynomial sequences of binomial-type arising in graph theory

MaRDI QIDQ405133zbMATH OpenFDO

Authors Jonathan Schneider

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.6174, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p43

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

binomial typechromatic polynomial

Mathematics Subject Classification ID

Umbral calculus (05A40) Combinatorial aspects of tessellation and tiling problems (05B45) Polyominoes (05B50) Graph polynomials (05C31)

Abstract: In this paper, we show that the solution to a large class of "tiling" problems is given by a polynomial sequence of binomial type. More specifically, we show that the number of ways to place a fixed set of polyominos on an $nimesn$ toroidal chessboard such that no two polyominos overlap is eventually a polynomial in $n$, and that certain sets of these polynomials satisfy binomial-type recurrences. We exhibit generalizations of this theorem to higher dimensions and other lattices. Finally, we apply the techniques developed in this paper to resolve an open question about the structure of coefficients of chromatic polynomials of certain grid graphs (namely that they also satisfy a binomial-type recurrence).

Review text

Summary: In this paper, we show that the solution to a large class of ``tiling problems is given by a polynomial sequence of binomial type. More specifically, we show that the number of ways to place a fixed set of polyominos on an \(n\times n\) toroidal chessboard such that no two polyominos overlap is eventually a polynomial in \(n\), and that certain sets of these polynomials satisfy binomial-type recurrences. We exhibit generalizations of this theorem to higher dimensions and other lattices. Finally, we apply the techniques developed in this paper to resolve an open question about the structure of coefficients of chromatic polynomials of certain grid graphs (namely that they also satisfy a binomial-type recurrence).

Recommendations

• scientific article; zbMATH DE number 6957158
• Combinatorial chessboard tilings
• Rook Theory. II: Boards of Binomial Type
• Counting Tilings by Taking Walks in a Graph
• On a sequence of sparse binomial-type polynomials

Cites work

• A new subgraph expansion for obtaining coloring polynomials for graphs
• General structural results for Potts model partition functions on lattice strips
• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• Linked-cluster expansion of the graph-vertex coloration problem
• On the foundations of combinatorial theory. VIII: Finite operator calculus
• The limit of chromatic polynomials
• Tutte polynomials and related asymptotic limiting functions for recursive families of graphs

Cited in

(10)

• On the operations of sequences in rings and binomial type sequences
• Sequences of binomial type with persistent roots
• Polynomials counting nowhere-zero chains in graphs
• Binomial sequences
• Genus polynomials of ladder-like sequences of graphs
• Bivariate affine Gončarov polynomials
• scientific article; zbMATH DE number 2127721 (Why is no real title available?)
• On generalized binomial series and strongly regular graphs
• On a sequence of sparse binomial-type polynomials
• Sequences of binomial type with polynomial coefficients

This page was built for publication: Polynomial sequences of binomial-type arising in graph theory

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