Mathematical Sciences Seminar - Applications and Studies in Modular Decomposition
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
The modular decomposition is a powerful tool for describing combinatorial structures (such as graphs, tournaments, posets or permutations) in terms of smaller ones. Since its appearance in a talk by Fraisse in the 1950s, and first appearance in print by Gallai in the 1960s, it has appeared in a wide variety of settings ranging from game theory to combinatorial optimisation. In this talk, after discussing some of these various historical settings, I will present a number of different settings where the modular decomposition has influenced my own research, including the enumeration and structural theory of permutations (in particular the general study of well-quasi-ordering), and -- quite unrelatedly -- recent connections made with the celebrated reconstruction conjecture. Of increasing importance to this work has been our growing understanding of the "prime" structures: those that cannot be broken down into smaller structures under the modular decomposition. Started by Schmerl and Trotter in the early 1990s, there is now an industry of researchers looking at the fine structure of these objects, and I will present some recent work in this area. Taker a "broader" view, we also know, in the case of permutations, a Ramsey-theoretic result for these prime structures: every sufficiently long prime permutation must contain a subpermutation belonging to one of three families. However, it still remains to translate this result into one for graphs, and I will close by exploring some of the difficulties and differences discovered in our attempts to make this conversion.
Contact name:
Department of Economics, Mathematics and Statistics