The combinatorics of pattern-avoiding matrices

• Thesis title in Czech: Kombinatorika matic bez zakázaných vzorů
• Thesis title in English: The combinatorics of pattern-avoiding matrices
• Key words: zakázané vzory|matice|permutace|Wilfova ekvivalence
• English key words: forbidden patterns|matrices|permutations|Wilf equivalence
• Academic year of topic announcement: 2020/2021
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: doc. RNDr. Vít Jelínek, Ph.D.
• Author: Mgr. David Mikšaník - assigned and confirmed by the Study Dept.
• Date of registration: 15.09.2021
• Date of assignment: 17.09.2021
• Confirmed by Study dept. on: 29.09.2021
• Date and time of defence: 10.02.2023 09:00
• Date of electronic submission: 05.01.2023
• Date of submission of printed version: 09.01.2023
• Date of proceeded defence: 10.02.2023
• Opponents: doc. RNDr. Martin Klazar, Dr.

Guidelines

Uchazeč se seznámí se stávajícími enumerativními a strukturálními výsledky v oblasti výzkumu matic bez zakázaných vzorů, s hlavním důrazem na výsledky týkající se Wilfovy ekvivalence. Následně odvodí vlastní výsledky v této oblasti. Hlavní důraz bude kladen na "řídké" vzory, tedy vzory tvořené maticemi nul a jedniček, které mají v každém řádku i v každém sloupci nejvýše jednu jedničku, a jsou tedy zobecněním permutačních matic.

References

Einar Steingrímsson: Generalized permutation patterns – a short survey, in: S. Linton, N. Ruškuc, V. Vatter (eds): Permutation Patterns; Cambridge University Press, 2010.

Daniela Battaglino, Mathilde Bouvel, Andrea Frosini and Simone Rinaldi: Permutation classes and polyomino classes with excluded submatrices, Mathematical Structures in Computer Science 27(2), 157-183 (2017).