Doktorandské kolokvium KAI - Pavol Kollár (24.11.2025)
v pondelok 24.11.2025 o 13:10 hod. v miestnosti I 9
Prednášajúci: Pavol Kollár
Názov: Combinatorial problems -- a place where classical enumeration fails
Termín: 24.11.2025, 13:10 hod., I/9
Abstrakt:
Combinatorial problems are, by their very nature, interesting and daunting at the same time. These types problems are approachable and can be explained with very little technical background and yet one can ask deep questions that require powerful machinery to approach answers and solutions to such questions.
In this talk we consider two such problems. One considers symmetries of graphs and generalises these concepts to the realm of permutation group theory and so-called "r-regular families of permutations". This project is continued work from previous years and we will report on our progress. The second problem generalises the classical antidictionary problem, where one wishes to distinguish between words that do not contain certain subwords and the ones that do, into two dimensions. This technique developed to tackling the classical antidictionary problem is useful in searching algorithms, especially the ``string searching'' algorithms. We will also see a famous class of graphs, so-called de Bruijn graphs, and how they are related to this two dimensional problem.