You are cordially invited to the M.S. Thesis Defense Presentation
“GENERATING TREE METHOD AND APPLICATIONS TO PATTERN-AVOIDING INVERSION SEQUENCES”
Melis Gezer, M.S. Student in Mathematics
Abstract: The study of enumerative and probabilistic aspects of pattern-avoiding combinatorial structures like permutations, sequences, and lattices has motivated the development of distinct methodologies. Over the past fifty years, extensive literature has emerged on pattern-avoiding permutations. Recently, researchers have turned their attention to pattern-avoiding inversion sequences, revealing intriguing insights in this domain.
An inversion sequence, denoted as e=e(1)e(2)…e(n), consists of non-negative integers where e(i)
The initial part of this thesis delves into an enumeration method based on generating trees and the kernel method. This approach provides a systematic means to enumerate various pattern classes I_n(B). We discuss its advantages and limitations by applying this method to distinct patterns. Subsequently, we establish an explicit bijection between 0321-avoiding inversion sequences and 0312-avoiding inversion sequences. This bijection preserves five statistics, including the number of zeros, the number of distinct elements, and the number of repeated elements. This resolves one of the fourteen conjectured cases for classes avoiding patterns of length four.
In the final part of the thesis, we address the sampling problem for pattern-avoiding inversion sequences. Sampling uniformly from I_n(B) for a given pattern set B and large n presents challenges due to pattern-restriction conditions. Brute-force algorithms can only provide uniform samples for sequences of length around 10 on a personal computer. To overcome this limitation, we have designed sampling algorithms capable of generating approximately uniform samples for sequences of length around 1000. The sampled data enable us to gain insight into the typical structure of pattern-restricted inversion sequences and compare distinct patterns.
This study was partially supported by TÜBİTAK grant no: 120F352. Numerical calculations were conducted at TÜBİTAK ULAKBİM’s High Performance and Grid Computing Center, as well as on servers provided by the Computer Engineering Department of Bilkent University.
Advisor: Asst. Prof. Dr. Gökhan Yıldırım
Date: May 16, 2024
Time: 11:00
Place: SA141 – Mathematics Seminar Room