Search

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

By using a symbolic method, known in the literature as the classical umbral calculus, a symbolic representation of Lévy processes is given and a new family of time-space harmonic polynomials with respect to such processes, which includes and generalizes the exponential complete Bell polynomials, is introduced. The usefulness of time-space harmonic polynomials with respect to Lévy processes is that it is a martingale the stochastic process obtained by replacing the indeterminate x of the polynomials with a Lévy process, whereas the Lévy process does not necessarily have this property. Therefore to find such polynomials could be particularly meaningful for applications. This new family includes Hermite polynomials, time-space harmonic with respect to Brownian motion, Poisson-Charlier polynomials with respect to Poisson processes, Laguerre and actuarial polynomials with respect to Gamma processes , Meixner polynomials of the first kind with respect to Pascal processes, Euler, Bernoulli, Krawtchuk, and pseudo-Narumi polynomials with respect to suitable random walks. The role played by cumulants is stressed and brought to the light, either in the symbolic representation of Lévy processes and their infinite divisibility property, either in the generalization, via umbral Kailath-Segall formula, of the well-known formulae giving elementary symmetric polynomials in terms of power sum symmetric polynomials. The expression of the family of time-space harmonic polynomials here introduced has some connections with the so-called moment representation of various families of multivariate polynomials. Such moment representation has been studied here for the first time in connection with the time-space harmonic property with respect to suitable symbolic multivariate Lévy processes. In particular, multivariate Hermite polynomials and their properties have been studied in connection with a symbolic version of the multivariate Brownian motion, while multivariate Bernoulli and Euler poly

We introduce an infinite family of lower triangular matrices ¡(s), where °s n;i counts the standard Young tableaux on n cells and with at most s columns on a suitable subset of shapes. We show that the entries of these matrices satisfy a three-term row recurrence and we deduce recursive and asymptotic properties for the total number ¿s(n) of tableaux on n cells and with at most s columns.

We define an analogue of signed Eulerian numbers fn;k for involutions of the symmetric group and derive some combinatorial properties of this sequence. In particular, we exhibit both an explicit formula and a recurrence for fn;k arising from the properties of its generating function.

La Teoria di Ramsey, che esplora le intersezioni sorprendenti tra ordine e caos, rappresenta un'area di ricerca affascinante nella Teoria dei Grafi, promettendo di svelare come, in qualsiasi sistema sufficientemente ampio e complesso, emergono inevitabilmente pattern e strutture. La presente tesi mira a guidare il lettore attraverso la Teoria di Ramsey, iniziando con un'esposizione della Teoria dei Grafi e proseguendo con un'analisi dei principi e delle applicazioni più recenti della Teoria di Ramsey. La tesi presenta un'introduzione rigorosa alla Teoria dei Grafi, esponendo le sue definizioni fondamentali, teoremi principali e problemi noti, con un focus particolare sui problemi di colorazione. Questa base teorica permette di apprezzare appieno la complessità e la bellezza intrinseche della Teoria di Ramsey quando applicata alla Teoria dei Grafi. Successivamente, il testo esplora la Teoria di Ramsey classica, discutendo la sua fondazione, i teoremi chiave, e illustrando come concetti apparentemente semplici possano avere implicazioni profonde e sorprendenti in contesti più ampi. Inoltre, la tesi approfondisce la relazione tra la Teoria dei Grafi e quella di Ramsey, esaminando come queste aree si influenzino reciprocamente e come la colorazione dei grafi riveli nuove prospettive all'interno della Teoria di Ramsey. L'analisi si conclude con uno studio sui numeri di Ramsey Arcobaleno e sulle loro applicazioni, offrendo una nuova dimensione alla discussione e mostrando l'ampio spettro di possibilità che la Teoria di Ramsey apre per la ricerca futura.