An official website of the United States government
The special purpose sorting operation, context directed swap (CDS), is an example of the block interchange sorting operation studied in prior work on permutation sorting. CDShas been postulated to model certain molecular sorting events that occur in the genome maintenance program of some species of ciliates. We investigate the mathematical structure of permutations not sortable by the CDSsorting operation. In particular, we present substantial progress towards quantifying permutations with a given strategic pile size, which can be understood as a measure of CDSnon-sortability. Our main results include formulas for the number of permutations in [Formula: see text] with maximum size strategic pile. More generally, we derive a formula for the number of permutations in [Formula: see text] with strategic pile size [Formula: see text], in addition to an algorithm for computing certain coefficients of this formula, which we call merge numbers.
more »
« less
POP-STACK SORTING AND ITS IMAGE:PERMUTATIONS WITH OVERLAPPING RUNS
Pop-stack sorting is an important variation for sorting permutations via a stack. A single iteration of pop-stack sorting is the transformation T : S_n -> S_n that reverses all the maximal descending sequences of letters in a permutation. We investigate structural and enumerative aspects of pop-stacked permutations – the permutations that belong to the image of Sn under T. This work is part of a project aiming to provide the full combinatorial analysis of sorting with a pop-stack, as it was successfully done for sorting with a stack (though, even in this case, some famous problems are still open). The first results already show that pop-stack sorting has a very rich combinatorial structure, and leads to surprising phenomena.
more »
« less
- Award ID(s):
- 1764012
- PAR ID:
- 10181643
- Date Published:
- Journal Name:
- Acta mathematica Universitatis Comenianae
- Volume:
- LXXXVIII
- Issue:
- 3
- ISSN:
- 0862-9544
- Page Range / eLocation ID:
- 395-402
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Optimizing expensive to evaluate black-box functions over an input space consisting of all permutations of d objects is an important problem with many real-world applications. For example, placement of functional blocks in hardware design to optimize performance via simulations. The overall goal is to minimize the number of function evaluations to find high-performing permutations. The key challenge in solving this problem using the Bayesian optimization (BO) framework is to trade-off the complexity of statistical model and tractability of acquisition function optimization. In this paper, we propose and evaluate two algorithms for BO over Permutation Spaces (BOPS). First, BOPS-T employs Gaussian process (GP) surrogate model with Kendall kernels and a Tractable acquisition function optimization approach to select the sequence of permutations for evaluation. Second, BOPS-H employs GP surrogate model with Mallow kernels and a Heuristic search approach to optimize the acquisition function. We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly. Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for combinatorial spaces. To drive future research on this important problem, we make new resources and real-world benchmarks available to the community.more » « less
-
Evil-avoiding permutations, introduced by Kim and Williams in 2022, arise in the study of the inhomogeneous totally asymmetric simple exclusion process. Rectangular permutations, introduced by Chirivì, Fang, and Fourier in 2021, arise in the study of Schubert varieties and Demazure modules. Taking a suggestion of Kim and Williams, we supply an explicit bijection between evil-avoiding and rectangular permutations in $$S_n$$ that preserves the number of recoils. We encode these classes of permutations as regular languages and construct a length-preserving bijection between words in these regular languages. We extend the bijection to another Wilf-equivalent class of permutations, namely the $$1$$-almost-increasing permutations, and exhibit a bijection between rectangular permutations and walks of length $2n-2$ in a path of seven vertices starting and ending at the middle vertex.more » « less
-
Abstract We introduce and study a one parameter deformation of the polynuclear growth (PNG) in (1+1)-dimensions, which we call the $$t$$-PNG model. It is defined by requiring that, when two expanding islands merge, with probability $$t$$ they sprout another island on top of the merging location. At $t=0$, this becomes the standard (non-deformed) PNG model that, in the droplet geometry, can be reformulated through longest increasing subsequences of uniformly random permutations or through an algorithm known as patience sorting. In terms of the latter, the $$t$$-PNG model allows errors to occur in the sorting algorithm with probability $$t$$. We prove that the $$t$$-PNG model exhibits one-point Tracy–Widom Gaussian Unitary Ensemble asymptotics at large times for any fixed $$t\in [0,1)$$, and one-point convergence to the narrow wedge solution of the Kardar–Parisi–Zhang equation as $$t$$ tends to $$1$$. We further construct distributions for an external source that are likely to induce Baik–Ben Arous–Péché-type phase transitions. The proofs are based on solvable stochastic vertex models and their connection to the determinantal point processes arising from Schur measures on partitions.more » « less
-
Let $$G$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$\Gamma=\mathrm{Cay}(G,T)$$ be a Cayley graph of $$G$$. The graph $$\Gamma$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph $$\Gamma$$ in terms of the second eigenvalues of certain subgraphs of $$\Gamma$$. Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$, and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leqslant 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
