Rational generating functions for grid classes with forest graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.