Discrete Mathematics Seminars

• 4 Jun
  2014 Semigroup theory
  Amit Kuber and David Wilding
  
  
• 28 May
  2014 Introduction to Cellular Automata
  Joe Razavi
  
  
  Abstract (click to view)

  A cellular automaton is a simple discrete dynamical system. Its states are (arbitrary) colourings of a regular grid of cells using a (fixed) finite set of colours. The cellular automaton is an "update" function from states to states, with the property that to work out what the updated colour of a cell is, we need only know what the colouring looked like in a finite neighbourhood of that cell.
  
  The fun of them is the Curtis-Hedlund-Lyndon Theorem: they are exactly the functions which commute with the symmetries of the grid and which are continuous with respect to a certain topology.

• 21 May
  2014 On the number of tilting modules for Dynkin quivers via polytopes
  Lutz Hille (Münster)
  
  
  Abstract (click to view)

  The number of tilting modules is classical known for type A and type D and recently attracted attention again in the work of Ringel and his coauthors. Moreover, certain closely related numbers also have been considered: the number of rigid modules, the number of exceptional sequences, the number of cluster tilting modules and the number of tilting complexes.
  
  The aim of this talk is to relate all these numbers and to unify the computation, so that it is not case by case anymore. Moreover, the number of tilting modules does not depend on the orientation, however, so far, the computation depends on a choice of the orientation of the quiver. The principal idea is to define certain polytopes, so that the volume of these polytopes coincides with the number of tilting modules. Using this approach, we obtain several recursion formulas that relate the these numbers and allow to compute them in one strike for all Dynkin quivers and all orientations.

• 14 May
  2014 Coxeter groups and non-crossing partition graphs
  Aram Dermenjian
  
  
  Abstract (click to view)

  Given a set of reflections one can generate a group known as a Coxeter group. Coxeter groups are not only geometric in nature, but also have interesting combinatoric side. By interpreting Coxeter groups as noncrossing partition graphs we can more easily use combinatorial methods already present to find such things as the Coxeter-Catalan and Fuss-Catalan numbers of the Coxeter group.
  
  In this seminar I will look at how we can interpret the classical Coxeter groups as noncrossing partition graphs and give their associated Coxeter-Catalan and Fuss-Catalan numbers. No previous knowledge on Coxeter groups or noncrossing partition graphs is required.

• 7 May
  2014 Posets and Spectra
  Amit Kuber
  
  
  Abstract (click to view)

  A spectrum is a topological space that illuminates certain properties of a given structure. Associated with a unital ring are two spectra—the prime spectrum and the max-spectrum; both are topologized using Zariski topology but only the former is a functorial construction. I will recall the definitions and properties of these spectra in the talk.
  
  One can associate a simplicial complex to a (locally) finite poset, called order complex, and study its homological/homotopical properties, but the order complex forgets a lot of information present in the poset. The main aim of this talk is to present two constructions of simplicial sets associated with a (locally) finite poset which "look" a lot like the prime spectrum and the max-spectrum; rather convincingly only the former is functorial. Both these constructions reflect the order structure of the (chains of the) poset. This is joint work with David Wilding.

• 30 Apr
  2014 A literal approach to enumeration
  David Wilding
  Article
  Abstract (click to view)

  Suppose you want to specify a sequence of natural numbers (perhaps the sequence counts the number of combinatorial objects of a given type). How will you do it? One standard approach is to come up with a 'generating function' for the sequence, but—to my mind at least—generating functions can often obscure the combinatorial meaning of a sequence. I will present a more literal and intuitive notation that can be used to specify certain sequences, and I will describe how to translate a sequence written in this notation into a computationally efficient procedure for actually enumerating the sequence. This will be a light-hearted talk with lots of examples!

• 2 Apr
  2014 Spaces Between the Discrete and the Continuous
  Joe Razavi
  
  Abstract (click to view)

  If you asked a continuous and a discrete mathematician to think of a theory of "closeness", one might think of topology, while the other might picture (a certain class of) graphs. These are different manifestations of a single idea: Cech closure spaces. In this talk we will look a few aspects of this conceptual unity, and investigate the relationship between the category of closure spaces and its subcategory of topological spaces.

• 26 Mar
  2014 Interplay between combinatorics and Galois theory
  Goran Malic
  
  
  Abstract (click to view)

  In the 1980's Grothendieck proposed a far-reaching program of studying the orbits of the absolute Galois group G$G$ over \mathbf Q$\mathbf Q$. The most fundamental part of this program is the action of G$G$ on bipartite graphs embedded cellularly onto Riemann Surfaces. This action has many interesting properties: it has been shown that the orbits of the action are always finite, and for example if a tree belongs to an orbit, then every other member of that orbit is also a tree. The orbits themselves carry an invariant of the action called the field of moduli which is constructed in a way so that it corresponds to a number field. So, in a hand-wavy sense, biparite graphs are "visual representations" of number fields.
  
  In this talk I shall explain in more detail the interaction between combinatorics of cellular bipartite graphs and Galois theory and, if time permits, use it to prove a theorem of Birch, Chowla, Hall and Schinzel concerning the difference x^3-y^2$x^3-y^2$ in about 16 minutes (the original proof took 16 years).

• 19 Mar
  2014 A geometry of 7-point planes
  David Ward
  Notes
  Abstract (click to view)

  The classification of finite simple groups gives four families of groups whose union is precisely the set of all finite simple groups. However, when are two such groups isomorphic to one another?
  
  In this talk we will show that the alternating group of degree 8 is isomorphic to the matrix group PSL(4,2) by considering group actions on a geometry of 7-point planes. No prior knowledge of geometries is required.

• 12 Mar
  2014 Homotopical algebra
  Amit Kuber and David Wilding
  
  
  Abstract (click to view)

  Simplicial objects in categories generalise chain complexes, and give us a way to generalise some ideas of homological algebra to certain categories. The resulting theory—called homotopical algebra—can be thought of as a "non-linear" version of homological algebra. This goes back to observations of Dold and Kan regarding the analogy between topological homotopy theory and homological algebra. We will describe the structure present on the categories that admit such a homotopy theory ('model categories'; not to be confused with model theory) and we will illustrate the details using topological spaces, sets and simplicial sets.

• 5 Mar
  2014 How to measure Rank, Length, or Dimension
  Harold Simmons
  Slides
  Abstract (click to view)

  One of these words is often used when we attach an ordinal to some gadget as an indication of how complicated it is. For instance you may have heard of the Cantor-Bendixson rank for a topological space, or the Socle length for a module, or the Krull and Gabriel and Boyle dimensions for a module. It doesn't matter if you have never heard of these. It doesn't matter too much if you are not familiar with ordinals.
  
  I will try to explain the general principle using the much simple notions of the Width and the Breadth of a lattice. I will show how it is often done, and how it should be done.

• 26 Feb
  2014 Stanley-Reisner rings
  Nic Clarke
  
  
  Abstract (click to view)

  To every simplicial complex on n$n$ vertices we can associate a ring called the Stanley-Reisner ring. These rings are quotients of a polynomial ring in n$n$ variables by a squarefree monomial ideal. Using the correspondence I will outline how some problems from combinatorics can be solved using commutative algebra and vice versa. In particular I will outline the proof of the upper bound theorem, giving a bound on the number of faces of a simplicial sphere, of a given dimension, with n$n$-vertices.

• 20 Feb
  2014 Testing primality "quickly"
  Matthew Taylor
  
  
  Abstract (click to view)

  Ever since the formulation of complexity classes in the 1960s, mathematicians have got closer and closer to finding a "quick" algorithm for testing whether a given number n$n$ is prime. In 2002, an Indian computer scientist and two of his undergraduate students finally cracked the problem. Their paper not only made the Annals of Mathematics, but was also given column inches in the New York Times. It was big news.
  
  But what does "quick" mean? To answer this, I'll be providing a layman's introduction to Turing machines, time complexity and a certain million-dollar problem—followed by an explanation of why methods like the Sieve of Eratosthenes aren't quite as "quick" as you might think. Of course, I'll also go through the algorithm itself!

• 12 Feb
  2014 Matrices over residuated lattices
  David Wilding
  Notes
  Abstract (click to view)

  Residuated lattices simultaneously generalise lattice-ordered groups and the structures used to model various many-valued logics (e.g., Boolean algebras, Heyting algebras and MV-algebras). Matrices over residuated lattices are of interest in data analysis (specifically formal concept analysis) and tropical mathematics, and the linear algebra of such matrices can be surprisingly similar to that of matrices over a field. I will describe some of the ways in which linear algebra over residuated lattices is like—and is unlike—linear algebra over fields.

• 5 Feb
  2014 Tiling problems and undecidability
  Francis Southern
  
  
  Abstract (click to view)

  A simple way to show the undecidability of a logic is by a reduction from the domino tiling problem. This is the problem of deciding if a finite set of dominoes can tile the \mathbf N\times\mathbf N$\mathbf N\times\mathbf N$ plane in a way which preserves some adjacency conditions (like how the numbers must match on adjacent "normal" dominoes). I'll briefly outline what a domino system is and why the domino tiling problem is undecidable, then I'll outline a concrete example by proving the undecidability of the two-variable fragment of first-order logic augmented with three equivalence relations (the details of the particular logic aren't hugely important, but I'll define it properly and explain what gives it the expressive power which leads to undecidability).

• 30 Jan
  2014 Number theory and dynamical systems—the missing link
  Dave Naughton
  
  
  Abstract (click to view)

  In 1979 Harry Furstenberg gave an alternate, ergodic theoretic proof of Szemeredi's theorem. Szemeredi's theorem says that any subset of the natural numbers with some (yeah I will define it proper) upper density property contains arbitrarily long arithmetic progressions. This gave rise to what is now known as ergodic Ramsey theory, a subject with which I have a rather unhealthy obsession with. In this talk I will give a brief introduction to symbolic dynamical systems, and use results involving the notion of recurrence to prove 3 really nice and incredibly simple results in combinatorial number theory. Problems which can easily be rephrased as graph colouring problems (although the proofs are a bit grim!) No prior knowledge of dynamical systems or ergodic theory will be required!

• 22 Jan
  2014 Domestic string algebras and the Ziegler spectrum
  Rosie Laking
  
  
  Abstract (click to view)

  The Ziegler spectrum \mathrm{Zg}_R$\mathrm{Zg}_R$ is a topological space associated to the category Mod-R$R$ of (right) modules over a ring R$R$. The aim of this talk is to introduce the spectrum with an emphasis on the points themselves—that is, the indecomposable pure-injective R$R$-modules.
  
  Using an example from the representation theory of finite-dimensional algebras we hope to illustrate how the (infinite-dimensional) pure-injective modules often arise naturally alongside their finite-dimensional counterparts. This is one of the many properties that has motivated the study of pure-injective modules, and hence the Ziegler spectrum, following a paradigm shift away from the traditional emphasis on the finite-dimensional modules.

• 11 Dec
  2013 Partitions, Bell polynomials, and binomial enumeration
  Nige Ray
  
  
  Abstract (click to view)

  The underlying theme of this talk concerns various algebraic and combinatorial constructions that can be made in terms of partially ordered sets of partitions. These include formal differential operators and their duals, namely binomial sequences of polynomials in a single variable. I hope to describe examples such as falling factorials, Abel polynomials, and Bell polynomials, and mention applications to Lagrange inversion and binomial enumeration; I might also make fleeting reference to applications to formal group laws and heavy-duty calculations in algebraic topology.

• 4 Dec
  2013 A cell decomposition of decorated Moduli Spaces (and the Kontsevich Volume)
  Goran Malic
  
  
  Abstract (click to view)

  The decorated Moduli Space of genus g$g$ curves with n$n$ marked points is the product M_{g,n}\times\mathbf R_+^n$M_{g,n}\times\mathbf R_+^n$ where \mathbf R_+$\mathbf R_+$ are the positive reals. It admits a cell decomposition indexed by ribbon graphs, ie. ordinary graphs that are thickened to a surface with boundary. The original moduli space M_{g,n}$M_{g,n}$ can be recovered via a natural projection from the decorated moduli space to the n$n$-dimensional positive reals whose fibers are homeomorphic to M_{g,n}$M_{g,n}$.
  
  If time permits, I will also speak about how the cells of this decomposition correspond to convex polytopes and admit a volume form. This allows us to define a volume V_{g,n}$V_{g,n}$ of M_{g,n}$M_{g,n}$ called the Kontsevich volume which is of special importance in String Theory.

• 13 Nov
  2013 Minkowski's convex body theorem and its applications
  Simon Baker
  
  
  Abstract (click to view)

  I will give a proof of Minkowski's convex body theorem. We will then prove Lagrange's four squares theorem (my favourite theorem) as a very simple corollary.

• 6 Nov
  2013 The combinatorial revolution in knot theory
  Andrew Davies
  
  
  Abstract (click to view)

  Classical knot theory concerns embeddings of circles into \mathbf R^3$\mathbf R^3$ up to homotopy. It is often easier to project such 'knots' to the plane and work with diagrams that have over and under-crossing information. From such a diagram one can obtain codes by labelling arcs or semi-arcs, but there are codes which do not arise from a planar diagram. In this seminar I will speak about how this has led to the consideration of generalised diagrams, their geometric motivation, and the peculiar algebraic structures that arise in tandem.

• 30 Oct
  2013 Four equivalences in graph theory
  Jamie Phillips and David Ward
  
  
  Abstract (click to view)

  In this discussion session we will illustrate the power of graph theory by showing how four different results regarding matchings of graphs, systems of distinct representatives (also know as transversals) of finite sets and partitions of posets are all connected by four equivalent graph-theoretic results; Dilworth's Theorem, König's Theorem, the König-Egervary Theorem and Hall's Marriage Theorem.
  
  We will prove a number of these equivalences, and—if time permits—illustrate a number of the natural applications to areas such as the decomposition of doubly stochastic matrices, and the existence of a transversal of any finite group that is both a right and left transversal simultaneously.

• 23 Oct
  2013 An introduction to simplicial sets and simplicial homotopy theory
  Nic Clarke
  
  
  Abstract (click to view)

  Simplicial sets are in many ways a generalisation of simplicial complexes and can be expressed purely combinatorially. By a theorem of Quillen they give a combinatorial way to study the homotopy of topological spaces. The aim of this talk is to explain enough of the theory of simplicial sets to state this theorem. I will start with the basic definition and then describe how constructions from topology have analogous constructions for simplicial sets, concentrating primarily on homotopy theory. I will then introduce the Kan condition and two functors (the geometric realisation and singular space functors) between the category of simplicial sets and topological spaces. We will then have everything we need to state Quillen's theorem. I will try to give plenty of examples for anyone who isn't familiar with simplicial complexes or homotopy theory.

• 16 Oct
  2013 Graphs associated to the symmetric group
  David Ward
  
  
  Abstract (click to view)

  When trying to determine properties of finite groups, it can be advantageous to look at various graphs associated to a given group. Examples of such graphs include Cayley graphs, commuting graphs and local fusion graphs.
  
  In this talk we will see that when our group is a symmetric group and we restrict our attention to a conjugacy class of involutions, then some powerful results about commuting and local fusion graphs can be obtained by analysing a special type of graph called an x-graph.

• 9 Oct
  2013 An introduction to various derivation systems for propositional logic
  Harold Simmons
  Slides
  Abstract (click to view)

  The long term aim was (and still is) to develop a derivation system that will classify formal proofs in terms of complexity or 'cost'. There are three general kinds of such systems (that I will mention).
  
  Hilbert systems, which most of you will have seen. These are more or less useless for the stated aim.
  
  Natural Deduction systems, which do look nice and easy, but have hidden daemons. Most have you will have used such a system but will not have been told that it is such a system.
  
  Gentzen systems, which do everything we want, but turn out to be very costly.
  
  I will explain how these systems work, how they interact with each other, how they produce completeness, and how cost can be measured.

• 2 Oct
  2013 A tropical landscape—and how to shape it
  Matthew Taylor
  
  
  Abstract (click to view)

  In a brief recap then continuation of my talk from the MRSC on Tuesday, I'll be going into detail on some of my research in tropical algebra over the past year.
  
  Tropical maths is a relatively new area of study which has a dedicated group at Manchester. Much of the early work of the algebraists in the group was on the structure of tropical matrices under matrix multiplication; my work ties into this a little, but concerns the tropical analog of real vector spaces and isomorphisms between them. How can we move these things around tropical space? Which isomorphisms are "nice"? What does "nice" even mean?
  
  To answer these questions, we'll need a lot of semigroup theory and a dab of linear algebra. I won't be assuming much, so all this will be covered and the talk should be accessible to all.

• 25 Sep
  2013 The random graph
  Mohsen Khani
  
  
  Abstract (click to view)

  The random graph is the unique (up to isomorphism) countably infinite graph which satisfies the following property (*)-n$n$ for all natural n$n$'s. (*)-n$n$: if X$X$ and Y$Y$ are two distinct sets of vertices each of which having n$n$ elements, then there is a vertex with edges going to all vertices in X$X$ and to none of the vertices in Y$Y$. The random graph arises in so many ways. For the model theorists, it is the Fraisse limit of a class of finite graphs whose theory, T$T$, gives us information about the theory of large finite graphs: T$T$ is the almost sure theory of graphs.

Other seminars

• Upcoming seminars
• September 2013–June 2014
• October 2012–May 2013