Below you'll find an overview of the past seminars in this series, specifically those held in 2012. The seminars are listed in reverse chronological order, most recent first.
Friday 18 May - Ryan Martin (Iowa State University)
Forbidden posets, the Boolean lattice and flag algebras
The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: $A\subset B,C\subset D$. A diamond-free family in the $n$-dimensional Boolean lattice is a subposet such that no four elements form a diamond. Note that elements $B$ and $C$ may or may not be related.
There is a diamond-free family in the $n$-dimensional Boolean lattice of size $(2-o(1)){n\choose\lfloor n/2\rfloor}$. In this talk, we show that any diamond-free family in the $n$-dimensional Boolean lattice has size at most $(2.25+o(1)){n\choose\lfloor n/2\rfloor}$. Furthermore, we show that the so-called Lubell function of a diamond-free family in the $n$-dimensional Boolean lattice is at most $2.25+o(1)$, which is asympotically best possible.
This is joint work with Lucas Kramer and Michael Young, both of Iowa State University.
Friday 11 May - Horst Martini (University of Technology, Chemnitz, Germany)
Some problems and results in Minkowski Geometry
The axiomatic foundations of the geometry of finite-dimensional real Banach spaces (Minkowski spaces) are due to Hermann Minkowski, and over a period of more than 100 years many results have been obtained in this direction. The more analytical part of this theory is summarized in the monograph "Minkowski Geometry" of A. C. Thompson (Cambridge University Press, 1996), and there is no analogous collection of related results in the spirit of Discrete and Computational Geometry. We will give some overview on results of this type, obtained recently and showing that also very elementary questions are still open and interesting as research in the geometric properties of Minkowski spaces.
Thursday 3 May - Andreas Wuerfl (Technische Universität München, Munich)
Planar subgraphs - a threshold for the number of edges
A graph is called planar if it can be drawn in the plane in such a way that its edges do not cross. We define the planarity of G to be the maximum number of edges in a planar subgraph of G. Finding such a maximum planar subgraph is a hard problem. Instead we will present lower bounds on the number of its edges. In particular we will be interested in the connection between minimum degree and planarity.
This dependence has been studied before for various minimum degrees. So we were surprised to find a jump in the evolution of the planarity at minimum degree n/2. This is joint work with T. Luczak and A. Taraz.
Tuesday 17 April - Massimo Gobbino (University of Pisa)
The Monopolist’s Problem: from an economic model to calculus of variation
No abstract.
Friday 16 March - Garth Dales (Leeds)
Second duals of algebras of continuous functions and measures
We first look at algebras of continuous functions on a compact space K, and their second duals. This is the algebra of continuous functions on the hyper-Stonean cover of K, which we shall describe. Then we shall consider the second dual of algebras of measures on a locally compact group (usually the circle group), and see the extent to which there is a product on this second dual that throws light on the original algebra. The story involves Stone-Cech compactifications, Borel functions, and ultrafilters.
The talk is related to a joint memoir:
H. G. Dales, A. T.-M. Lau, and D. Strauss, Second duals of measure algebras, Dissertationes Math., to appear soon
Thursday 8 March - Giacomo Zambelli (LSE)
Cutting planes, lattice-free sets and sublinear functions
Cutting planes play a central role in integer programming. Gomory Mixed-Integer cuts (GMI) are arguably the most widely exploited among general purpose cutting planes. General frameworks encompassing GMI cuts have been proposed about forty years ago by Gomory and by Balas, where GMIs can be interpreted as "intersection cuts" for the so called "corner polyhedron". Recently, there has been a revived interest in the IP community for this approach, mostly focused on the study of so called "valid functions" - which give general formulas to generate cutting planes - and on the correspondence between the "best" valid functions and maximal lattice-free convex sets. In this talk we will discuss some of these recent developments.
The talk is based on joint works with Amitabh Basu, Manoel Campelo, Michele Conforti and Gerard Cornuejols.
Friday 2 March - Penny Haxell (Waterloo)
On packing and covering in hypergraphs
We discuss some recent developments on the following long-standing problem known as Ryser's conjecture. Let $H$ be an $r$-partite $r$-uniform hypergraph. A matching in $H$ is a set of disjoint edges, and we denote by $\nu(H)$ the maximum size of a matching in $H$. A cover of $H$ is a set of vertices that intersects every edge of $H$. It is clear that there exists a cover of $H$ of size at most $r\nu(H)$, but it is conjectured that there is always a cover of size at most $(r-1)\nu(H)$.
Thursday 1 March - Peter Keevash (Queen Mary)
Matching and Packing
Matching theory is a large field with many directions of research, both in practical algorithms and combinatorial theory. In this talk I will aim to show some of the breadth of the subject, and some recent advances on matching theory for hypergraphs (joint work with Richard Mycroft). Informally speaking, we show that the obstructions to perfect matchings are geometric, and are of two distinct types: `space barriers' from convex geometry, and `divisibility barriers' from arithmetic lattice-based constructions. We apply our theory to the solution of two open problems on hypergraph packings: the minimum degree threshold for packing tetrahedra in 3-graphs, and Fischer's conjecture on a multipartite form of the Hajnal-Szemeredi Theorem
Thursday 16 February - Chris Argasinski (University of Sussex)
In which currency are payoffs paid in evolutionary games?
The talk will be devoted to the problem of the mechanistic
interpretation of mathematical (game theoretic) notions to describe
particular phenomenon (by example of population dynamics and natural selection). In the standard approach to evolutionary games and replicator dynamics, differences in fitness can be interpreted as an excess from the mean Malthusian growth rate in the population. In the underlying reasoning, related to an analysis of "costs" and "benefits", there is a silent assumption that fitness can be described in some kind of "units". However, in most cases these units of measure are not explicitly specified. Then the question arises: are these theories testable? How can we measure "benefit" or "cost"? A natural language, useful for describing and justifying comparisons of strategic "cost" versus "benefits", is the terminology of demography, because the basic events that shape the outcome of natural selection are births and deaths. However, when we apply this approach then abstract "fitness" splits into two types of payoffs describing reproductive success (number of offspring) and individual survival. In effect an individual is playing simultaneously two types of games that can affect each other in few ways. This extension of mathematical structure used to describe natural process dramatically changes quantitative predictions and our understanding of this process. This shows how important a clear mechanistic interpretation of mathematical notions is to the proper understanding of natural phenomena and to avoid artefacts.
Thursday 9 February - Bharath K Sriperumbudur (UCL)
Reproducing Kernel Space Embeddings and Metrics on Probability Measures
In this talk, I will present a generalization to the characteristic function of a probability measure, by embedding measures into reproducing kernel Hilbert spaces (RKHSs). The motivation to consider such a generalization is that for an appropriate choice of RKHS, this provides a powerful and simple method of dealing with higher-order statistics of random variables (not necessarily be defined on R^n), which can then be exploited in many statistical applications like homogeneity/independence/goodness-of-fit testing, density estimation, etc. For this generalized notion to be useful in practice, it is critical that the above mentioned embedding is injective, i.e., the embedding should uniquely characterize all probability measures. I will discuss how this problem is related to the approximation properties of RKHS and then present novel and simple characterizations for the embedding to be injective. I will then introduce and address an important question on the choice of kernels, and conclude with my very recent results on embedding probability measures into reproducing kernel Banach spaces by discussing the advantages/disadvantages over its RKHS counterpart.
Joint work with Kenji Fukumizu (The Institute of Statistical Mathematics), Arthur Gretton (Gatsby Computational Neuroscience Unit, UCL), Gert Lanckriet (UC San Diego) and Bernhard Scholkopf (Max Planck Institute for Intelligent Systems)
2 February - Wei Yang (University of Warwick)
Mean field games and nonlinear Markov processes
We present mean field games methodology in a fully general setting, based on the theory of nonlinear Markov processes. The realization of this methodology includes three steps. First, we prove the well-posedness of general kinetic equations with coupled functional parameters. Second, we proved the well-posedness and sensitivity for the HJB equation. Finally, we justify the mean field games as a proper approximation of large population systems as N goes to infinity.
Mean field games appear in the papers by P. L. Lions and co-authors and P. Cains and co-authors, where the underlying processes are all Brownian motions. We develop this methodology for a fully general setting with arbitrary underlying Markov processes of interactions and prove convergence results with 1/N convergence rate. These estimates are new even for the diffusion case. This is a joint work with Vassili Kolokoltsov and Jiajie Li.
26 January - Greg Sorkin| (LSE)
3-Dimensional Random Assignment Problems
The 2-dimensional assignment problem (minimum cost matching) is solvable in
polynomial time, and it is known that a random instance of size n, with entries
chosen independently and uniformly at random from [0,1], has expected cost
tending to pi^2/6. In dimensions 3 and higher, there are natural Axial and
Planar assignment generalizations. Both are NP-complete, but what is the
expected cost for a random instance, and how well can a heuristic do? The
asymptotic behavior remains an open question. For 3-dimensional Planar
assignment, we give a ln n approximation algorithm, and for Axial assignment, an
unrelated n^eps approximation algorithm. In higher dimensions, both algorithms
fail dismally.
Joint work with Alan Frieze
19 January - Julia Bõttcher (LSE)
Julia Bõttcher (LSE)
Tight Hamilton cycles in random hypergraphs
I present a method for finding a k-uniform tight Hamilton cycle in a k-uniform random hypergraph with edge probability p=n^{eps-1} for every positive eps with high probability.
This gives a polynomial time randomised algorithm for this problem. The techniques we developed for this also have (more interesting) applications for finding powers of Hamilton cycles (and thus K_r-factors) in pseudorandom graphs, which I will also try to outline.
Joint work with Peter Allen, Hiep Han, Yoshiharu Kohayakawa, Yury Person.
12 January 2012 - Peter Allen (LSE)
The chromatic thresholds of graphs
Given a graph H, the chromatic threshold of H is the infimum of reals d>0 such that there exists C=C(d) with the following property. For every n, every H-free graph with n vertices and minimum degree dn has chromatic number at most C.
The problem of determining the chromatic thresholds of graphs was initiated by Erdős and Simonovits in 1973, but no non-trivial case was solved until Thomassen found the chromatic threshold of the triangle in 2002. In 2010, Łuczak and Thomassé, and Lyle, gave solutions for two different families of tripartite graphs. In this talk, we will give the complete solution.
This is joint work with Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa and Robert Morris.