New Bounds on Roller Coaster Permutations


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


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).
Como Citar

Selecione um Formato
BOTLER, Fábio; NETTO, Bruno L.. New Bounds on Roller Coaster Permutations. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 6. , 2021, Evento Online. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2021 . p. 50-53. ISSN 2595-6116. DOI: