Seminari di Combinatoria al Dini:

I seminari si svolgono al Dipartimento di Matematica e Informatica "Ulisse Dini", in viale Morgagni 67/a, a Firenze.

1. Luca Ferrari (Università di Firenze)

Data e aula: Giovedì 7 novembre 2019, ore 14.30, aula Tricerri

Titolo: Dyck algebras, interval temporal logic and posets of intervals [slides]

Abstract: We investigate a natural Heyting algebra structure on the set of Dyck paths of the same length. We provide a geometrical description of the operations of pseudocomplement and relative pseudocomplement, as well as of regular elements. We also find a logic-theoretic interpretation of such Heyting algebras, which we call Dyck algebras, by showing that they are the algebraic counterpart of a certain fragment of a classical interval temporal logic (also known as Halpern-Shoham logic). Finally, we propose a generalization of our approach, suggesting a similar study of the Heyting algebra arising from the poset of intervals of a finite poset using Birkhoff duality. In order to illustrate this, we show how several combinatorial parameters of Dyck paths can be expressed in terms of the Heyting algebra structure of Dyck algebras together with a certain total order on the set of atoms of each Dyck algebra.

2. Giulia Palma (Università di Pisa)

Data e aula: Mercoledì 13 novembre 2019, ore 11:00, aula Tricerri

Titolo: Combinatorial properties of degree sequences of 3−uniform hypergraphs arising from saind sequences [slides]

Abstract: A fundamental and widely investigated notion related both to graphs and to hypergraphs is the characterization of their degree sequences, indeed they provide us with extremely helpful tools to model and gather information about a wide range of statistics of complicated systems. The study of the degree sequences of k−uniform hypergraphs has been a long-standing open problem for the case k > 2, until very recently when A. Deza et al. proved that for any fixed integer k ≥ 3, this problem is NP−complete. Our present work aims to study degree sequences that arise from sn-sequences (i.e. integer non increasing sequences), that can be find in Deza’s NP−completeness proof. We mainly focus on saind sequences (i.e. sn−sequences containing all the integers from n to −[n + (n − 1) − 1]), we analyze the combinatorial properties of the derived degree sequences in order to characterize them and to find a polynomial time algorithm that realizes one of the associated 3−uniform hypergraphs and we show that there are connections with other families of combinatorial structures known in the literature (e.g. symmetric Dyck paths with three peaks, integer partitions in two parts, bracelets with n + 3 beads, genotype frequency vectors possible for a sample of p diploid individuals at a biallelic genetic locus with a specific major allele). The results are obtained by borrowing some mathematical tools from recent research areas involving discrete mathematics: Discrete Tomography, Enumerative Combinatorics and Combinatorics on words.

3. Antonio Bernini (Università di Firenze)

Data e aula: Martedì 19 novembre 2019, ore 11:00, aula Tricerri

Titolo: From cross-bifix-free strings to non-overlapping matrices [slides]

Abstract: Two strings (possibly the same) are said cross-bifix-free if any non-empty proper prefix of one of them is different from any non-empty proper suffix of the other one, and viceversa. Two matrices (possibly the same) are non-overlapping when it is not possible to shift one on the other one in such a way that the entries of their intersection match. Moving from known sets of cross-bifix-free of strings, new sets of non-overlapping matrices are defined where matrices have variable dimensions.

4. Giulio Cerbai (Università di Firenze)

Data e aula: Mercoledì 27 novembre 2019, ore 11:30, aula Tricerri

Titolo: Transporting patterns from ascent sequences to Fishburn permutations [slides]

Abstract: We initiate the development of a theory of patterns transport from ascent sequences to Fishburn permutations and viceversa, using a well known bijection introduced in a paper by Bousquet-Melou, Claesson, Dukes and Kitaev. Since the notion of pattern is rather complicated on ascent sequences, our goal is to shift some related problems to the realm of Fishburn permutations, solve them and finally recollect the desired results via our transport theory. In doing so, we prove some useful results regarding ascent sequences and modified sequences. We also prove (a part of) a conjecture proposed by Duncan and Steingrimsson.

5. Einar Steingrimsson (University of Strathclyde)

Data e aula: Martedì 3 dicembre 2019, ore 15:30, aula Tricerri

Titolo: The symmetry of (area, bounce), a story of failures

Abstract: The bounce statistic on Dyck paths is defined as follows (up to a normalization): starting at the right end of a path, draw a line from the x-axis following the rightmost upstep (at 45 degree angle) until you hit a downstep. Then follow that downstep and continue in a straight line until you hit the x-axis. Turn up and left, at 45 degree angle, until you hit a down step, then go down to the x-axis again. Repeat this until you come to the origin. Bounce is the sum of the x-coordinates of the points where you hit the x-axis. It has been proved by analytic methods (Garsia-Haiman and Haglund) that the bistatistic (area, bounce) has a symmetric distribution, that is, that (area, bounce) is equidistributed with (bounce, area), where area is the (normalized) area between the path and the x-axis. No combinatorial proof has been found, despite some effort, and the fact that such a proof might be valuable in the study of diagonal harmonics, where the analytic proof appeared. I will describe some of my attempts to find a combinatorial proof, all of which have been unsuccessful, although some minor nice results have emerged along the way, regarding statistics on triangulations of n-gons and 312-avoiding permutations.

6. Veronica Guerrini (Università di Pisa)

Data e aula: Martedì 17 dicembre 2019, ore 11:30, aula 7

Titolo: Metagenomic analysis through the eBWT [slides]

Abstract: Metagenomics refers to the sequencing of microbial DNA collected directly from the environment. The analysis of an environmental sample is particularly important to understand the microbial composition. Thus, of fundamental importance is to identify with precision the microorganisms that are present in a metagenomic sample by comparing the biological sequences therein and classify them by assigning to specific taxa. The metagenomic classification problem can be formalized as a sequence similarity problem. With the aim of providing a new method for the metagenomic classification, which is assembly-free and alignment-free by nature, we exploited the combinatorial properties of the Burrows-Wheeler transform (BWT) and its extension to a set of strings (eBWT) as to define a new notion of similarity between sequences. Such a new notion is enhanced by an intuitive idea: the greater is the similarity between two sequences, the greater is the number of substrings they share. We evaluated our alignment-free strategy against the state-of-the-art tools performing metagenomic classification. The overall accuracy of our approach is comparable to that of the other tools, and experiments on simulated datasets show the highest F1 score - harmonic mean of precision and recall - gained by our approach.

7. Massimo Nocentini (Università di Firenze)

Data e aula: Martedì 14 gennaio 2020, ore 14:30, aula Tricerri

Titolo: Dancing Links: an educational pearl [slides]

Abstract: This talk aims to show *Dancing Links* (re)-introduced by Donald Knuth and it can be regarded as an educational pearl. In Donald's words: Suppose x points to an element of a doubly linked list; let L[x] and R[x] point to the predecessor and successor of that element. Then the operations L[R[x]] ← L[x], R[L[x]] ← R[x] (1) remove x from the list; every programmer knows this. But comparatively few programmers have realized that the subsequent operations L[R[x]] ← x, R[L[x]] ← x (2) will put x back into the list again. The element denoted by x has been deleted from its list; why would anybody want to put it back again? An interactive program may need to revert to a former state; oth, another typical application arises in backtrack programs, which enumerate all solutions to a given set of constraints. The beauty of (2) is that operation (1) can be undone by knowing only the value of x. We can apply (1) and (2) repeatedly in complex data structures that involve large numbers of interacting doubly linked lists. This process causes the pointer variables inside the global data structure to execute an exquisitely choreographed dance; hence I like to call (1) and (2) the technique of *dancing links*. We would like to show our implementation which uses plain DoubleLink and DoubleLinkedList objects and some applications to exact cover problems such as sudoku and N-Queen.

8. Matteo Cervetti (Università di Trento)

Data e aula: Giovedì 30 gennaio 2020, ore 11:30, aula Tricerri

Titolo: Enumerative Combinatorics of the Matching Pattern Poset [slides]

Abstract: A matching of semilength n is a partition of {1,...,2n} in blocks with two elements, i.e., a graph on {1,...,2n} such that every vertex has degree one. Given two matchings σ and tau, we will say that σ is a pattern of τ , and write σ < τ , when σ can be obtained from τ by deleting some edges of τ and consistently relabelling its vertices, and we will call the resulting poset matching pattern poset. In this context we will present some enumerative results and open problems about pattern avoidance for small patterns, in particular we will focus on the enumeration of the matchings avoiding the juxtapposition of two patterns, working out explicit enumerative formulas for at least two new classes of matchings avoiding a single pattern (and all their Wilf equivalents), namely the patterns {{1,3},{2,4},{5,7},{6,8}} and {{1,3},{2,4},{5,8},{6,9},{7,10}}. Finally, we will also introduce the notion of unlabeled pattern as an equivalence class of usual patterns, i.e., an unlabeled graph, and provide enumerative results for some classes of matchings avoiding an unlabeled pattern of semilength three, namely {{1,6},{2,4},{3,5}}, {{1,2},{3,6},{4,5}} and {{1,6},{2,5},{3,4}}.

9. Vincent Vajnovszki (Université de Bourgogne, Dijon)

Data e aula: Martedì 26 ottobre 2021, ore 14:30, aula Anfiteatro

Titolo: The equidistribution of some Mahonian statistics over permutations avoiding a pattern of length three

Abstract: We prove the equidistribution of several multistatistics over some classes of permutations avoiding a 3-length pattern. We deduce the equidistribution, on the one hand of inv and foze′′ statistics, and on the other hand that of maj and makl statistics, over these classes of pattern avoiding permutations. Here inv and maj are the celebrated Mahonian statistics, foze′′ is one of the statistics defined in terms of generalized patterns in the 2000 pioneering paper of Babson and Steingrìmsson, and makl is one of the statistics defined by Clarke, Steingrìmsson and Zeng in 1997. These results solve several conjectures posed by Amini in 2018.

10. Vincent Vajnovszki (Université de Bourgogne, Dijon)

Data e aula: Giovedì 28 ottobre 2021, ore 11:45, aula Anfiteatro

Titolo: Popularity of patterns over d-equivalence classes of words and permutations

Abstract: Two same length words are d-equivalent if they have same descent set and same underlying alphabet. In particular, two same length permutations are d-equivalent if they have same descent set. The popularity of a pattern in a set of words is the overall number of copies of the pattern within the words of the set. We show the far-from-trivial fact that two patterns are d-equivalent if and only if they are equipopular over any d-equivalence class, and this equipopularity does not follow obviously from a trivial equidistribution.

11. Lapo Cioni (Università di Firenze)

Data e aula: Lunedì 20 dicembre 2021, ore 12:00, aula Anfiteatro

Titolo: The interval posets of permutations seen from the decomposition tree perspective

Abstract: The interval poset of a permutation is the set of intervals of a permutation, ordered with respect to inclusion. It has been introduced and studied recently by Bridget Tenner. We study this poset from the perspective of the decomposition trees of permutations, describing a procedure to obtain the former from the latter. We then solve some of the open problems that were posed and some other enumerative problems using techniques from symbolic and analytic combinatorics. Finally, we compute the Möbius function on such posets.