Rational generating functions for grid classes with forest graphs

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.