New Bounds on Roller Coaster Permutations

• Fábio Botler UFRJ http://orcid.org/0000-0003-2028-199X
• Bruno L. Netto UFRJ https://orcid.org/0000-0002-1560-4988

DOI: https://doi.org/10.5753/etc.2021.16378

Resumo

A roller coaster is a permutation \pi that maximizes the sum $\t(\pi) = \sum_{\tau\in X(\pi)}\id(\tau)$, where \(X(\pi)\) denotes the set of subsequences of \(\pi\) with cardinality at least \(3\); and \(\id(\tau)\) denotes the number of maximal increasing or decreasing subsequences of contiguous numbers of \(\tau\). We denote by \(\t_{\max}(n)\) the value \(\t(\pi)\), where \(\pi\) is a roller coaster of \(\{1,\ldots,n\}\), for \(n\geq 3\). Precise values of \(\t_{\max}(n)\) for \(n\leq 13\) were presented in \cite{AhmedTanbir}. In this paper, we explore the problem of computing lower bounds for \(\t_{\max}(n)\). More specifically, we present a cubic algorithm to compute $\t(\pi)$ for any given permutation $\pi$; and an Integer Linear Programming model to obtain roller coasters. As a result, we improve known lower bounds found in the literature for $n \leq 40$.

Palavras-chave: Permutation, Integer Linear Programming, Lower Bounds, Roller Coaster

Referências

Adamczak, W. (2017). A note on the structure of roller coaster permutations. Journal of Mathematics Research, 9(3):75–79.

Ahmed, T. and Snevily, H. (2013). Some properties of roller coaster permutations. Bulletin of the Institute of Combinatorics and its Applications, 68.

Gurobi Optimization, L. (2021). Gurobi optimizer reference manual.

The Sage Developers (2020). SageMath, the Sage Mathematics Software System (Version 9.2). https://www.sagemath.org.