Doktorandské kolokvium KAI - Pavol Kollár (10.3.2025)
v pondelok 10.3.2025 o 13:10 hod. v miestnosti I/9
Prednášajúci: Pavol Kollár
Názov: Counting an Unreasonable Amount of Objects in a Reasonable Amount of Time
Termín: 10.3.2025, 13:10 hod., I/9
Abstrakt:
Considering all possible cases is good when you can write them down and consider them one-by-one. Things get much more complicated, however, when the number of cases grows so big, not even a computer could tractably consider all them.
Such is the case with our line of research, where we use advanced algebraic and computational methods to solve combinatorial problems. Our topic of study today features graphs with high symmetry levels, which have a hierarchy in them based on “how close to being a Cayley graph” they are. The deciding criterion turns out to be an interesting object of study in its own right, generalising transitivity of group actions.
In the talk we build upon our previous work of using generating polynomials, which is a general purpose algorithm, to get upper bounds on the number of r-regular families. Once this algorithm is in place, we need to understand what makes inputs bad and good, so that we can pick our algorithm’s inputs in a smart and useful way. Last, but not least, we present a probabilistic extension of a brute-force algorithm that lets us approximately count the number of solutions to a problem that would otherwise be untractable.