Please note, this is archived content and is no longer being updated. It is provided for historical records. Links on the pages may be broken or redirect to our current site.
Archived
material
You are here: MIMS > events > seminars > discrete maths
MIMS

# Discrete Mathematics Seminars

The discrete mathematics seminar series is an informal series of research and general interest seminars given by staff and postgraduates. Please contact Amit Kuber or David Wilding if you would like to receive announcements of upcoming seminars or if you are interested in giving a seminar. Any topic that could (even loosely) be described as discrete mathematics is welcome.

• 20 May
2013
How Cantor invented the ordinals, and how many ordinals can we name
Harold Simmons
Slides
Abstract (click to view)

Cantor had to invent the ordinals to carry out a quite complicated analysis, what is now known as the Cantor-Bendixson process. There is a much simpler version of this process using trees, and this does not need any technical knowledge. I will explain this tree-process and indicate how it goes 'beyond the infinite'. I will then illustrate how Cantor began to name the ordinals.

• 13 May
2013
Numerical solutions to ODEs and the Hopf algebra of rooted trees
Amit Kuber
Slides
Abstract (click to view)

Numerical solutions of equations associated with the flow of a (non-linear) vector field has been an interest for centuries. Runge-Kutta (RK) methods are the standard methods implemented in all modern software. The technique behind these methods involves comparing weighted coefficients of different Taylor series. On our way, we will meet "tree factorials" and "tree derivatives".

John Butcher—a New Zealand mathematician developed the theory of Runge-Kutta methods further. He showed that numerical approximation obtained by RK methods can be realised as an algebraic approximation of the characters of a certain Hopf algebra, often called Connes-Kreimer algebra. It is said that "Butcher's work on the classification of numerical integration methods is an impressive example that concrete problem-oriented work can lead to far-reaching conceptual results".

• 8 May
2013
An introduction to (block) design theory
David Ward
Notes
Abstract (click to view)

A (block) design is a set together with a collection of subsets that satisfy certain regularity conditions. Although easy to define and parametrise, designs play an important role in many areas of mathematics including geometry and group theory.

In this talk, the basic notions of design theory will be introduced and illustrative examples will be given. The importance of one such design—the Steiner system \mathrm S(5,8,24)$\mathrm S(5,8,24)$—will be explained. If time permits, applications to coding theory will be discussed.

• 29 Apr
2013
Grothendieck's dessin d'enfants and an action of the absolute Galois group
Goran Malic

Abstract (click to view)

In the 1980's Grothendieck dramatically shifted his interest from the most abstract of objects like varieties, schemes etc. to a surprisingly simple structure which he dubbed 'dessin d'enfant' (children's drawing). A dessin d'enfant (dessin for short) is essentially a bipartite graph embedded into an orientable compact surface.

Grothendieck discovered, much to his amazement, that there is a correspondence between the dessins and algebraic curves C$C$ endowed with a function f$f$ ramified over three values, both defined over the algebraic closure of the rationals. Therefore, the action of the absolute Galois group G$G$ over \mathbf Q$\mathbf Q$ on pairs (C,f)$(C,f)$ induces an action on the dessins and this action can be used to study the structure of G$G$.

In this talk I shall present an introduction to the theory of dessin d'enfants and describe some combinatorial invariants that arise from the action of G$G$ on the dessins.

• 22 Apr
2013
Diagrams in categories (discussion session)

Abstract (click to view)

Most of us wonder how (co)limits of a particular shape can be constructed in a category of our interest. We will lead a discussion on general theory behind construction of (co)limits in categories with the help of special (co)limits. We will also encourage to describe actual construction in some well-known categories like Set, AbGr, Group, Ring, Top etc.

• 15 Apr
2013
Colour symmetry
Jamie Phillips

Abstract (click to view)

Assume that one has a symmetrical geometric figure or ornamental design. This has associated with it a group of symmetries. Group theory affords a tool in studying and developing such designs. Colour symmetry is an extension of this approach.

The theory of colour symmetry was motivated by fields of chemistry and art. Shubnikov, in the 1940s, was the first to pioneer its development in crystallography. The Dutch artist Escher independently began to investigate the use of colour symmetry in his drawings.

In this talk I will define what is meant by a colour symmetry of a design, and introduce the notions of perfect colouring, partial colouring and compound colouring. Our illustrative examples will be planar figures but, time permitting, I will expand the theory to tilings of the plane and perhaps even designs in hyperbolic space. However far we get, you can rest assured that there will be plenty of pretty pictures to look at.

• 18 Mar
2013
The diamond lemma
Andrew Davies

Abstract (click to view)

In this seminar I will speak about a result from graph theory called the diamond lemma. It has many nice consequences in different areas of maths and in particular can be reformulated in terms of noncommutative algebras. I will cover both the original graph theoretic result and the way in which it can be applied noncommutatively (if that is a word…).

• 11 Mar
2013
String algebras
Rosie Laking

Abstract (click to view)

With an emphasis on string algebras as an illustrative example, I will give an overview of the strong connections between quivers (a.k.a. directed graphs) and the representation theory of finite-dimensional algebras. String algebras demonstrate this relationship particularly well since every indecomposable module over a string algebra can be thought of in terms of a walk through the associated quiver.

I will also mention the Auslander-Reiten quiver of a module category, whose revelatory power is described by Gabriel and Roiter as "a deus ex machina disentangling the jungle of indecomposables".

• 4 Mar
2013
Ramsey's theorem, Büchi automata and S1S (continued)
Markus Pfeiffer

Abstract (click to view)

After an introduction to Büchi automata we aim to prove that S1S, the second order theory of one successor, is decidable. The proof incorporates automata theory and logic and includes a nice real world application of the infinite Ramsey Theorem we learned about earlier.

• 25 Feb
2013
What is combinatorics? (continued)
Alexandre Borovik

Abstract (click to view)

I will argue that combinatorics, as it arises in the "mainstream" mathematics, can be seen as "elimination of continuous parameters". This formulation was coined by Israel Gelfand. Using some simple examples, I'll try to expand Gelfand's definition and explain why combinatorics is so important and special integral part of mathematics.

• 18 Feb
2013
The mathematical secrets of good algorithms
David Wilding

Abstract (click to view)

There is often an obvious, yet inefficient, algorithm for solving a given computational problem. An efficient algorithm is not always easy to find (if one exists at all), but sometimes the introduction of the right mathematical structure greatly aids the search. I will explain the mathematics behind the good algorithms for solving searching and sorting problems.

• 11 Feb
2013
Short impartial games and some useful set theory
Harold Simmons
Slides
Abstract (click to view)

There is a formal definition of a game developed in some detail by John Conway and others. The games we look at here are played between two people who take it in turns to make moves according to certain rules. Each play can have only finitely many moves, and the player who eventually can not move loses that play. There are many informal games of that kind, such as Nim, Kayles, and the Grundy games which I will look at in some detail.

I will describe the formal version of a short impartial and show that for each such game there is a winning strategy for one of the players. Surprisingly, this involves some rather simple set theory.

• 4 Feb
2013
Plane crystallographic groups and the Penrose tiling
Nic Clarke

Abstract (click to view)

Plane crystallographic groups are the symmetry groups of infinitely repeating patterns (tilings) in the plane. I will prove a classification theorem for these groups and give some examples. If I have time I will talk about Penrose tilings which are an interesting example of tilings with no translational symmetry.

• 28 Jan
2013
What is combinatorics?
Alexandre Borovik

Abstract (click to view)

I will argue that combinatorics, as it arises in the "mainstream" mathematics, can be seen as "elimination of continuous parameters". This formulation was coined by Israel Gelfand. Using some simple examples, I'll try to expand Gelfand's definition and explain why combinatorics is so important and special integral part of mathematics.

• 12 Dec
2012
Ramsey's theorem, Büchi automata and S1S
Markus Pfeiffer

Abstract (click to view)

After an introduction to Büchi automata we aim to prove that S1S, the second order theory of one successor, is decidable. The proof incorporates automata theory and logic and includes a nice real world application of the infinite Ramsey Theorem we learned about last week.

• 5 Dec
2012
Infinite Ramsey's theorem
Mohsen Khani

Abstract (click to view)

Assumptions: X$X$ is an infinite set, n$n$ and k$k$ are fixed natural numbers and F\colon[X]^n\to\{1,\dotsc,k\}$F\colon[X]^n\to\{1,\dotsc,k\}$ is a function that assigns a colour to each subset of X$X$ of size n$n$.

Conclusion: there is a subset Y$Y$ of X$X$ such that Y$Y$ is infinite and F$F$ assigns the same colour to each subset of Y$Y$ of size n$n$.

I will give a proof of this and finite Ramsey's theorem.

• 28 Nov
2012
Quivers, matrices and related constructions
Amit Kuber and David Wilding

Abstract (click to view)

We can relate the dimension of a path algebra of a quiver without relations with its adjacency matrix. This topic can be thought of in the intersection of linear algebra and graph theory. We can also realise the path algebra of a quiver as a particular instance of a more general construction in algebra. Discussion will be encouraged!

• 22 Nov
2012
A semigroup to gossip with
Marianne Johnson

Abstract (click to view)

In this talk I will describe a fun problem from the 1970's which concerns gossiping over the telephone. I'll introduce a monoid (that is, a semigroup with identity element) associated to this problem and describe a number of (equivalent) ways to view this object. I'll tell you what (little) I know about this "gossip monoid" and what questions remain. If time permits, I'll also describe a generalisation of the gossip monoid to a setting with unreliable telephone lines.

• 15 Nov
2012
Gelfand-Kirillov dimension of algebras
Andrew Davies

Abstract (click to view)

I will speak about a (vaguely) combinatorial object associated to algebras, namely Gelfand-Kirillov dimension. I will try to motivate why a good notion of dimension for noncommutative algebras is desirable yet elusive. I will also describe some basic examples, touch on a method to construct pathological ones, and end with a relatively recent result which has nice consequences for noncommutative algebraic geometry.

• 7 Nov
2012
The involution principle in partition theory
Matthew Taylor

Abstract (click to view)

Adding together integers is such a basic part of everyday maths; it's surprising how little we know about it! Since the mid-18th century, a pantheon of mathematical greats have pitted their wits against partition identities—equations concerning the ways in which we can sum positive integers with certain restrictions.

Bijections between the sets involved were a popular method of proof, but hit a roadblock early in the 20th century in the form of an identity discovered independently by Rogers and Ramanujan. I'll be going through how the problem was solved and the consequences it had for partition identities. By the end, you'll even be able to create your own identities! The talk will be almost entirely self-contained and should be accessible to all.

• 31 Oct
2012
How to "build" modules for group algebras
David Ward
Slides
Abstract (click to view)

Most of us have encountered modules of some kind at some point in our mathematical development. They arise in many different areas of mathematics, and roughly speaking involve an (additive) abelian group on which a ring acts. A specific class of modules occurs when our ring is a group algebra over a field. In such a situation our modules become vector spaces. But how do we create such modules in the first place?

One such approach involves defining things called presheaves on simplicial complexes, and combines combinatorics, linear algebra, group actions and even a very tiny bit of topology. In this talk, I will give a brief introduction to the methods involved, explaining all of the above terms in the process.

• 24 Oct
2012
Simple (simplicial) complexes
Amit Kuber

Abstract (click to view)

Sometimes pictures are the best ways to understand difficult pieces of mathematics. Venn diagrams, graphs, posets are amongst such representations. But graphs are just one-dimensional objects. Simplicial complexes are their generalisations to all non-negative integral dimensions.

I will talk about some areas of mathematics where simplicial complexes arise naturally and describe some constructions of obtaining new simplicial complexes from the existing ones. I will also talk about simplicial posets and multinerves if time permits.

• 17 Oct
2012
Computing orthogonal complements on finite tori
David Wilding
Slides
Abstract (click to view)

Many of us would be able to sketch the row space of a (sufficiently small!) real matrix, but what about the row space of a matrix whose entries are congruence classes of integers? As you'll see in the talk, it's possible, and actually quite fun, to draw such spaces and their orthogonal complements on the surface of a torus. I'll explain what an orthogonal complement is in this context, although you might well be able to guess, and I'll describe a nice way to compute such things.