Rational generating functions for grid classes with forest graphs
Let be a finite matrix defining a grid class , and let be the bipartite graph whose vertices represent the rows and columns of , with an edge whenever the corresponding entry of is nonzero. A generating function is rational if it is a quotient of polynomials. Forest rationality conjecture. If is a forest, then 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
- Sophie Huczynska and Vincent Vatter, “Grid classes and the Fibonacci dichotomy for restricted permutations”, arXiv:math/0602143 (2006).
Progress summary
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.