Bipartite characterization of rational POP generating functions
Bipartite characterization of rational POP generating functions
Let a POP class be a permutation class defined by avoidance of partially ordered patterns. Its generating function is the ordinary generating function of its counting sequence, and the class is bipartite when its defining partially ordered pattern has a bipartite underlying poset.
Bipartite characterization conjecture. A POP class has a rational generating function if and only if it is bipartite.
The conjecture strengthens the computational observation that the size- POP classes found with rational generating functions were bipartite and had regular insertion encodings. The supplied context notes that the available regular-insertion-encoding results do not prove that non-regular classes cannot have rational generating functions.
Sources & referencesView supporting material
Primary source
Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson, “Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding”, arXiv:2312.07716 (2023).
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
Sign in to submit a solution.
No solutions have been posted yet.