The strong rationality characterization for permutation classes

A permutation class is a class of permutations closed under taking patterns. A class is strongly rational if it and all of its subclasses have rational generating functions, and it is well-quasi-ordered if its permutations are well-quasi-ordered under pattern containment.

Strong rationality conjecture. A permutation class is strongly rational if and only if it is well-quasi-ordered and does not contain the class of 312312-avoiding permutations or any symmetry of it.

This conjecture seeks to characterize strong rationality using structural properties of permutation classes. The stated results establish the analogous characterization for subclasses of the 321321-avoiding permutations, while the general assertion remains open.

Sources & referencesView supporting material

Primary source

Michael H. Albert, Robert Brignall, Nik Ruškuc and Vincent Vatter, “Rationality for subclasses of 321-avoiding permutations”, arXiv:1602.00672 (2019).

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.