Maths Seminar Series: Graham Farr, Monash University – Powerful Sets: A Generalisation of Binary Linear Spaces
Thursday 7 November 2019 – 2.00pm – 3.00pm
The Mathematics Research Lab welcomes Graham Farr from Monash University to present his research.
Abstract
A set S of binary vectors, with positions indexed by E, is said to be a powerful code if, for all subsets X of E, the number of vectors in S that are zero in the positions indexed by X is a power of 2. By treating binary vectors as characteristic vectors of subsets of E, we say that a set S of subsets of E is a powerful set if the set of characteristic vectors of sets in S is a powerful code. Powerful sets (codes) in- clude binary linear codes (equivalently, cocircuit spaces of binary matroids), but much more besides. In this talk we investigate the combinatorial properties of powerful sets. We prove fundamental results on special elements (loops, coloops, frames, near-frames, and stars), their associated types of single-element extensions, various ways of combining powerful sets to get new ones, and constructions of nonlinear pow- erful sets. We show that every powerful set is determined by its collection of minimal nonzero members. Finally, we show that the number of powerful sets is doubly exponential, and hence that almost all pow- erful sets are nonlinear. (Joint work with Yezhou Wang, University of Electronic Science and Technology of China (UESTC).)
Bio
Graham Farr is a Professor in the Faculty of Information Technology at Monash University, Aus- tralia, and Co-Convenor of the cross-faculty Discrete Mathematics Research Group. He has served as Head of two separate Schools in the Faculty of I.T. He holds a DPhil in Mathematics from the University of Oxford and is a Fellow of the Australian Mathematical Society. In 2011 he received the Vice-Chancellor’s Award for Excellence in Postgraduate Supervision at Monash. Interests include combinatorial enumeration (es- pecially Tutte-Whitney polynomials), graph theory, algorithms, complexity, information theory and com- puter history. His work on Tutte-Whitney polynomials includes extensions to Boolean functions and arbi- trary weighted set systems, extensions using generalised minor operations with connections to statistical mechanics, relationships with some variations on classical duality including triality/trinity, their compu- tational complexity on lattice subgraphs, their algebraic properties, and their history. Since 2008 he has led Computer History Tours of Melbourne.