Sorting permutations with pattern-avoiding machines

2025-05-03 0 0 1.26MB 147 页 10玖币

侵权投诉

Universit`a di Firenze – Universit`a di Perugia – INdAM – CIAFM

DOTTORATO DI RICERCA

IN MATEMATICA, INFORMATICA, STATISTICA

CURRICULUM IN INFORMATICA

CICLO XXXIII

Sede amministrativa: Universit`a degli Studi di Firenze

Coordinatore Prof. Paolo Salani

Sorting permutations with

pattern-avoiding machines

Settore Scientiﬁco Disciplinare INF/01

Dottorando

Dott. Giulio Cerbai

Tutore

Prof. Luca Ferrari

Coordinatore

Prof. Paolo Salani

Anni 2017/2020

arXiv:2210.03621v1 [math.CO] 7 Oct 2022

A mio babbo

Acknowledgements

First, I thank my advisor Luca Ferrari, for being the kindest and most helpful

guide I could have asked for. His oﬃce door was always open, and the hours we

spent discussing combinatorics (and everything else) are countless. Regardless how

busy he was, he managed to carve out some time to answer my questions and hear

my thoughts. I owe him all my academic results: it is not much, but I hope more

will come in the future.

I thank Anders Claesson for raising the question upon which this entire work of

thesis is built, and for his precious teachings and insight. I thank him for having

invited me in Iceland for a month. He shared his oﬃce and treated me as an

equal from the ﬁrst moment, although the diﬀerence in our understanding and

knowledge was immense.

I thank Luca Ferrari, Antonio Bernini, Elena Barcucci and Renzo Pinzani for

welcoming me in the combinatorics family in Firenze.

I thank all the people I’ve worked with during my PhD, as well as those that

were kind enough to share their knowledge with me. Amongst them, Einar Ste-

ingr´ımsson, not only for his inspiring lessons and stimulating discussions, but also

for his introduction to the study of patterns on ascent sequences. Christian Bean,

for providing a lot of useful data. Jean-Luc Baril, Carine Khalil and Vincent

Vajnovszki, for the paper we wrote together.

Introduction

To characterize and enumerate permutations that can be sorted by two consecutive

stacks, connected in series, is amongst the most challenging open problems in

combinatorics. It is known that the set of sortable permutations is a class with

an inﬁnite basis, but the basis remains unknown. The enumeration of sortable

permutations is still missing as well. Several variants and weaker formulations

have been discussed in the literature, some of which are particularly meaningful.

For instance, West 2-stack sortable permutations are those that can be sorted

by making two passes through an increasing stack. To use an increasing stack

means to always perform a push operation, in a greedy fashion, unless adding

the next element would make the content of the stack not increasing, reading

from top to bottom. As it is well known, an increasing stack is optimal for the

classical problem of sorting with one stack, thus West’s device is arguably the

most straightforward generalization to two stacks of the orginal instance. This

monotonicity requirement can be equivalently expressed by saying that the stack

is 21-avoiding, again referring to the stack not being allowed to contain occurrences

of the pattern 21. The present work of thesis is nothing more than an attempt to

answer a question raised1by Claesson:

What happens if we regard the stack as σ-avoiding during the ﬁrst pass, for some

pattern σ, and 21-avoiding during the second pass?

The resulting device is called the σ-machine. A σ-machine is the natural gen-

eralization of West’s device obtained by replacing 21 with any pattern σ, during

the ﬁrst pass, and using the optimal algortithm, during the second pass. This

approach can be pushed even further by replacing σwith a set of patterns Σ,

obtaining a family of sorting devices which we call pattern-avoiding machines.

We devote this entire manuscript to the study of pattern-avoiding machines,

aiming to gain a better understanding of sorting with two consecutive stacks.

For speciﬁc choices of σ, we characterize and enumerate the set of permutations

1As a follow-up question of a related talk given by Ferrari and the current author at Permu-

tation Patterns 2018.

iii

that are sortable by the σ-machine, which we call σ-sortable. The combinatorics

underlying σ-machines and σ-sortable permutations is extremely rich. It often

displays geometric structure and reveals links with a great deal of discrete objects.

Certain patterns are particularly relevant. For instance, by setting σ= 21 we

get West’s device, while the 12-machine is similar to a device studied by Smith

(but uses a diﬀerent sorting algorithm). In order to sort the largest amount of

permutations, a sensible try is to set σ= 231: indeed a 231-stack constantly aims

to prevent the output of occurrences of 231, which is the well known requirement

that the input of a classical (increasing) stack has to satisfy in order to be sortable.

The thesis has the following structure:

In Chapter 3 we provide results that cover families of patterns by analyzing how

the choice of σaﬀects the structure of σ-sortable permutations. The most relevant

(and maybe surprising) is the proof that sets of σ-sortable permutations that are

not permutation classes are enumerated by the Catalan numbers, contained in

Chapter 3. If σ-sortable permutations form a class, it is the set of permutations

avoiding 132 and the reverse of σ. On the other hand, sets that are not classes

are really hard to characterize and enumerate. Amongst them, the only patterns

we are able to solve are 123 and 132. A description of 231-sortable permutations

remains unknown, as well as their enumeration. We then prove that σ-sortable

permutations avoid a bivincular pattern ξof length three, unless σis the skew-sum

of 12 minus a 231-avoiding permutation.

The pattern 123 is solved in Chapter 4. We provide a step by step construction

of 123-sortable permutations that leads to a bijection with a class of pattern-

avoiding Schr¨oder paths, whose enumeration is known.

The pattern 132 is solved in Chapter 5. We ﬁrst characterize 132-sortable

permutations as those avoiding 2314 and a mesh pattern of length three. The ob-

tained description is then exploited to determine their geometric structure. More

precisely, we show that 132-sortable permutations satisfy speciﬁc geometric con-

straints in the grid decomposition induced by left-to-right minima. Finally, we

deﬁne a bijection with a class of pattern-avoiding set partitions, encoded as re-

stricted growth functions.

In Chapter 6 we discuss a variant of pattern-avoiding machines where the ﬁrst

stack is (σ, τ)-avoiding, for a pair of patterns σand τ. We solve several pairs

of patterns of length three. We then determine an inﬁnite family of pairs where

sortable permutations are enumerated by the Catalan numbers.

In Chapter 7 we analyze some dynamical aspects of the σ-stack operator. We

introduce the notions of σ-sorted permutations,σ-fertility and eﬀective pattern.

We characterize eﬀective patterns, then we describe σ-sorted permutations and σ-

fertilities of the 123-machine.

In Chapter 8 we consider a natural generalization of σ-machines where input

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

UniversitadiFirenze{UniversitadiPerugia{INdAM{CIAFMDOTTORATODIRICERCAINMATEMATICA,INFORMATICA,STATISTICACURRICULUMININFORMATICACICLOXXXIIISedeamministrativa:UniversitadegliStudidiFirenzeCoordinatoreProf.PaoloSalaniSortingpermutationswithpattern-avoidingmachinesSettoreScienticoDisciplinareINF/01D...

展开>> 收起<<

Sorting permutations with pattern-avoiding machines.pdf

共147页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Sorting permutations with pattern-avoiding machines

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: