Rational generating functions for grid classes with forest graphs

At least 19 years old · documented by

Let MM be a finite matrix defining a grid class Grid⁡(M)\operatorname{Grid}(M), and let G(M)G(M) be the bipartite graph whose vertices represent the rows and columns of MM, with an edge whenever the corresponding entry of MM is nonzero. A generating function is rational if it is a quotient of polynomials. Forest rationality conjecture. If G(M)G(M) is a forest, then Grid⁡(M)\operatorname{Grid}(M) and all its subclasses have rational generating functions. The source describes this as a speculative extension of known results: permutation-matrix grid classes have eventually polynomial enumeration, while star-graph grid classes have rational generating functions. Its resolution is not given in the source.

References

Primary source

Sophie Huczynska and Vincent Vatter, “Grid classes and the Fibonacci dichotomy for restricted permutations”, arXiv:math/0602143 (2006).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.