The centrosymmetric growth-rate inequality for permutation classes

Let C\mathcal{C} be a permutation class. Write gr(C)\overline{\operatorname{gr}}(\mathcal{C}) for its upper growth rate and grrc(C)\overline{\operatorname{gr}}^{rc}(\mathcal{C}) for the upper rcrc-growth rate, obtained from the even-size centrosymmetric permutations in C\mathcal{C}. Centrosymmetric growth-rate conjecture.

grrc(C)gr(C).\overline{\operatorname{gr}}^{rc}(\mathcal{C})\leq\overline{\operatorname{gr}}(\mathcal{C}).

The conjecture asserts that the growth of even-size centrosymmetric elements cannot exceed the overall growth of the class. The paper proves the reverse inequality in several settings, including sum-closed rcrc-invariant classes and certain geometric grid classes, but the general inequality remains open.

Sources & referencesView supporting material

Primary source

Justin M. Troyka, “On the centrosymmetric permutations in a class”, arXiv:1804.03686 (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.