2025

October 22 (Wed) 11:00 am ; (joint with the CART seminar)

KIAS 1424 & Zoom https://kimsh.kr/vz

Veronica Kelsey (University of Manchester)

Title: Irredundant bases for permutation groups

Abstract: A base of a group $G \leq \mathrm{Sym}(Omega)$ is a sequence $\Lambda$ of points in $\Omega$ such that the identity is the only element of $G$ fixing $\Lambda$ pointwise. The size of the smallest base is denoted $\mathrm{b}(G, \Omega)$. The study of bases dates back to the 19th century but perhaps their most important use has been in computational group theory. There is a large computational saving when $|\Lambda|<<|\Omega|$, and so we’d ideally like to know $\mathrm{b}(G, \Omega)$. Sadly there is no known efficient algorithm for finding these minimal bases, and Blaha showed in 1992 that determining $\mathrm{b}(G,\Omega) \leq c$ for a given constant $c$ is NP-complete. Instead we consider irredundant bases which can be thought of as the “best worst case”. In this talk I will introduce all these concepts along with examples and discuss some of the recent work in this area.