Hyungryul Baik (KAIST),
Sang-hyun Kim, Javier de la Nuez-González, Carl-Fredrik Nyberg-Brodda, David Xu (KIAS),
Sanghoon Kwak (SNU)
Zoom https://kimsh.kr/vz
Meeting ID: 822 3235 0014
Passcode: 7998
Time Generally, Tuesdays or Thursdays 11 am KST
Length is typically for one-hour unless noted otherwise, although it's often extended by questions etc.
Mailing list Please contact one of the organizers to subscribe.
Google calendar subscribe to visgat google caldender to automatically add the upcoming seminars to yours!
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.