The combinatorics of pattern-avoiding matrices

• Název práce v češtině: Kombinatorika matic bez zakázaných vzorů
• Název v anglickém jazyce: The combinatorics of pattern-avoiding matrices
• Klíčová slova: zakázané vzory|matice|permutace|Wilfova ekvivalence
• Klíčová slova anglicky: forbidden patterns|matrices|permutations|Wilf equivalence
• Akademický rok vypsání: 2020/2021
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: doc. RNDr. Vít Jelínek, Ph.D.
• Řešitel: Mgr. David Mikšaník - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 15.09.2021
• Datum zadání: 17.09.2021
• Datum potvrzení stud. oddělením: 29.09.2021
• Datum a čas obhajoby: 10.02.2023 09:00
• Datum odevzdání elektronické podoby: 05.01.2023
• Datum odevzdání tištěné podoby: 09.01.2023
• Datum proběhlé obhajoby: 10.02.2023
• Oponenti: doc. RNDr. Martin Klazar, Dr.

Zásady pro vypracování

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.

Seznam odborné literatury

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).