Below you'll find an overview of the past seminars in this series from 2015. The seminars are listed in reverse chronological order, most recent first.
Thursday 17 December - Grzegorz Tomkowicz (G2 Education Center)
The Banach-Tarski Paradox and Games of Incomplete Information
Let G be a free group acting freely on a set X. We explore G-paradoxical decompositions of X in the spirit of Banach and Tarski by means of a finite data of information and the doubling conditions. We then relate our results to some open questions about equilibria in games of incomplete information.
Grzegorz Tomkowicz is a self-educated Polish mathematician who has made several important contributions to the theory of paradoxical decompositions and invariant measures.
Thursday 3 December - Thomas Bloom (Bristol)
Ramsey-equivalence of cliques
A graph G is Ramsey for another graph H if, under any two-colouring of the edges of G, there exists a monochromatic copy of H. Families of such graphs for fixed H have been studied for decades, but surprisingly, it is only recently that the property of these families being identical has been investigated. We say that H_1 and H_2 are Ramsey equivalent if whenever G is Ramsey for H_1 it is also Ramsey for H_2. The property of being equivalent to a complete graph K_n was recently investigated by Fox, Grinshpun, Liebenau, Person and Szabo, with great success, but left open the question of whether K_n is equivalent to K_n + K_{n-1} for n at least 4. In joint work with Anita Liebenau we have answered this question in the affirmative. I will sketch the proof, and describe this relatively young field and some of the beautiful open questions that remain.
This is joint work with joint with Anita Liebenau.
Thursday 26 November - Yufei Zhao (Oxford)
Large deviations in random graphs
What is the probability that the number of triangles in an Erdős–Rényi random graph exceeds its mean by a constant factor? In this talk, I will discuss some recent progress on this problem.
Already the order in the exponent of the tail probability was a long standing open problem until several years ago when it was solved by DeMarco and Kahn, and independently by Chatterjee. We now wish to determine the exponential rate of the tail probability. Thanks for the works of Chatterjee--Varadhan (dense setting) and Chatterjee--Dembo (sparse setting), this large deviations problem reduces to a natural variational problem. We solve this variational problem asymptotically, thereby determining the large deviation rate, which is valid at least for p > 1/n^c for some c > 0.
Based on joint work with Bhaswar Bhattacharya, Shirshendu Ganguly, and Eyal Lubetzky.
Tuesday 17 November - Liana Yepremyan (McGill)
The Local Stability Method and the Tur\'an numbers of extensions
The Tur\'an number of a graph G, denoted by ex(n,G), is the maximum number of edges in an G-free graph on n vertices. The Tur\'an density of a graph G, denoted by \pi(G), is the limit as n tends to infinity of the maximum edge density of an G-free graph on n vertices. Unless \pi(G)=0, it captures the asymptotic behaviour of ex(n,G).
During this talk I will discuss a method, which we call local stability method, that allows one to obtain exact Tur\'an numbers from Tur\'an density results. This method can be thought of as an extension of the classical stability method by generically utilizing Lagrangians and symmetrization. Using it, we solved a conjecture of Frankl and Füredi from 1980's and obtained the Tur\'an number of a hypergraph called generalized triangle, for uniformities 5 and 6. Further, our method is more generally applicable for determining Tur\'an numbers of so-called extensions.
This is joint work with Sergey Norin.
Thursday 12 November - Maura Paterson (Birkbeck)
Applications of Disjoint Difference Families
A difference set in a finite additive group G is a subset S of G with the property that the collection of differences between pairs of distinct elements of S contains each nonzero element of G precisely lambda times for some fixed lambda>0. Difference sets and their generalisation to difference families have long been studied in the context of combinatorial design theory. In this talk we will survey a range of generalisations of these concepts and consider examples of applications in cryptography and communications in which these more general structures arise in a natural way.
Tuesday 3 November - Andres Perea (Maastrict)
Forward induction reasoning versus equilibrium reasoning
In the literature on static and dynamic games, most rationalizability concepts have an equilibrium counterpart. In two-player games, the equilibrium counterpart is obtained by taking the epistemic conditions of the rationalizability concept and adding the following correct beliefs assumption: (a) each player believes that the opponent is correct about his beliefs, and (b) each player believes that the opponent believes that he is correct about the opponent's beliefs. In this talk I explain why there is no equilibrium counterpart to the forward induction concept of extensive-form rationalizability (Pearce (1984), Battigalli (1997)), epistemically characterized by common strong belief in rationality (Battigalli and Siniscalchi (2002)). The reason is that there are games where the epistemic conditions of common strong belief in rationality are logically inconsistent with the correct beliefs assumption. In fact, I show that this inconsistency holds for "most" dynamic games of interest.
Paper: http://epicenter.name/Perea/Papers/FI-Equilibrium.pdf
Thursday 29 October - Jie Han (Birmingham)
Dirac's Theorem for Hypergraphs
Cycles are fundamental objects in graph theory. A spanning cycle in a graph is also called a Hamiltonian cycle. The celebrated Dirac's Theorem in 1952 shows that every graph on $n\ge 3$ vertices with minimum degree at least $n/2$ contains a Hamiltonian cycle. In recent years, there has been a strong focus on extending Dirac’s Theorem to hypergraphs. We survey the results along the line and mention some recent progress on this problem.
Joint work with Yi Zhao.
Thursday 22 October - Anthony Nixon (Lancaster)
Rigidity of graphs on expanding spheres
A graph G is rigid if some (equivalently, all) generic realisation of G, in Euclidean space, admits no edge-length preserving continuous deformation of its vertices. For realisations in 1D the answer is simple and for 2D there is an elegant description of rigidity purely in terms of the graph, however for higher dimensions there is no known combinatorial characterisation. I will describe the basic theory of rigid graphs.
I will then move on to recent joint work with Bernd Schulze, Shin-Ichi Tanigawa and Walter Whiteley. We consider graphs realised on concentric d-spheres in d+1 dimensions where the radii of the spheres are allowed to vary independently. I will discuss, in terms of the dimension and the number of spheres varying at different rates, when combinatorial descriptions of rigidity are possible and when they are not. The appropriate combinatorial objects will be count matroids arising from submodular functions using coloured graphs.
Thursday 15 October - Mykhaylo Tyomkyn (Birmingham)
Strong Turán Stability
We study the behaviour of K_{r+1}-free graphs G of almost extremal size, that is, typically, e(G) = ex(n,K_{r+1}) − O(n). We show that such graphs must have a large amount of symmetry. In particular, if G is saturated, then all but very few of its vertices must have twins. As a corollary, we obtain a new proof of a theorem of Simonovits on the structure of extremal graphs with ω(G) ≤ r and χ(G) ≥ k for fixed k ≥ r ≥ 2.
Joint work with Andrew Uzzell.
Thursday 8 October - Ben Barber, Birmingham
Edge decompositions of graphs
An F-decomposition of a graph G is a partition of E(G) into copies of F. Determining whether a graph has an F-decomposition is NP-complete, but it is much easier to find 'fractional' decompositions. I'll explain the connection between these ideas and how it can be exploited to attack Nash-Williams' conjecture that every large graph on n vertices with minimum degree at least 3n/4, e(G) divisible by 3 and every degree even has a triangle decomposition.
Thursday 24 September - Stanislaw Spiez (Mathematical Institute of the Polish Academy of Sciences)
Borsuk-Ulam Equilibrium Theorem and Games
Abstract not available
Friday 18 September - Massimo Gobbino (Pisa)
Title and abstract not available
Thursday 25 June - Sylvain Sorin (University of Paris 6) On some advances in zero-sum repeated games
The purpose of this survey talk is to:
-
present briefly the topic and the main issues
-
describe some new approaches, results and directions of research. Topics include: uniform and asymptotic analysis, approachability, Shapley operator, stochastic games and games with incomplete information, link with games in continuous time, differential games and games with vanishing stage duration.
Thursday 18 June - Andre Nies (University of Auckland)
Interactions of computability and randomness
Randomness and computability are closely connected. We provide mathematical formulations of the two concepts for infinite sequences of bits. Then we discuss theorems showing the close relationship between the two concepts.
For a mathematician, randomness of an infinite sequence of bits (equivalently, a real) is usually understood probability-theoretically. Theorems about random objects hold outside some unspecified null class; for instance, a function of bounded variation is differentiable at every ''random'' real. It makes no sense to say that an individual real is random. In algorithmic randomness one introduces an effective notion of a null class, called a test. A sequence is random in that sense if it avoids each test. For instance, Chaitin's halting probability is random in the sense of Martin-Loef. A real is Martin-Loef random if and only if every computable function of bounded variation is differentiable at the real (Demuth 1975; Brattka, Miller and Nies, TAMS 2015). Effective randomness notions interact in fascinating ways with the computational complexity of sequences of bits. For instance, being far from Martin-Loef random is equivalent to being close to computable in a specific sense (Nies, Advances in Math, 2005).
Recent work of my PhD student A. Galicki addresses differentiability of monotone computable functions in higher dimensions. One connection to randomness is obtained via a result from optimal transport in the sense of Monge and Kantorevich.
Thursday 11 June - Milan Vojnovic (Microsoft Research)
Utility Sharing and Social Welfare
The framework of utility sharing games allows us to model situations in which individuals invest efforts in one or more production activities, which results in a utility of production that is shared amongst contributors according to a utility sharing mechanism. In these games, several factors may result in social inefficiency of an equilibrium outcome, including how the effort investments amount to the utility of production, the nature of production costs, the choice of utility sharing mechanism, and the existence of alternative options due to multiple available activities. In this talk, we will discuss some recent work on social efficiency of standard equilibrium outcomes, equilibrium outcomes that are stable with respect to coalitional deviations, and coalitional best-response dynamics.
Thursday 4 June - Sebastian Siebertz (TU Berlin)
Algorithmic graph structure theory for sparse graphs -- An overview and recent advances
Algorithmic graph structure theory attempts to explain for natural and important classes of graphs what kind of problems can be solved efficiently on these graphs and develop the corresponding graph structural and algorithmic techniques. A prototypical example from algorithmic graph structure theory is Courcelle's Theorem, stating that all properties of graphs of bounded tree-width that are definable in monadic second-order logic are decidable in linear time. Other important classes with good algorithmic properties are classes of bounded degree, planar graphs, and more generally, classes that exclude a fixed (topological) minor and many more.
As diverse as the examples above of graph classes with a rich algorithmic theory may appear, a feature all these classes have in common is that they are relatively sparse, i.e. graphs in these classes have a relatively low number of edges compared to the number of vertices. This suggests that this sparsity might be an underlying reason why many problems can be solved efficiently on these classes of graphs, even though they otherwise do not have much in common.
Nowhere dense classes were introduced by Nešetřil and Ossona de Mendez as a formalisation of classes of sparse graphs, which generalise all of the above graph classes. Nowhere density turns out to be a very robust concept with several seemingly unrelated natural characterisations and each characterisation yields different algorithmic techniques. We have shown that all properties of graphs that are definable in first-order logic are decidable in almost linear time on any nowhere dense class of graphs. It has been shown before that the first-order model-checking problem cannot be solved efficiently on any somewhere dense class which is closed under subgraphs (under a reasonable complexity theoretic assumption). This supports the intuition that nowhere dense classes are the natural limit for many algorithmic techniques for sparse graph classes.
In this talk, I am going to give an overview over characterisations of nowhere dense graphs and show examples of how these characterisations were recently used to obtain new algorithmic results.
Thursday 21 May - Allan Lo (Birmingham)
Edge-decompositions of graphs with high minimum degree
A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$ divides the greatest common divisor of the degrees of $G$, and $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. We extend this result to graphs which are allowed to be far from complete: we show that every sufficiently large $F$-divisible graph $G$ on $n$ vertices with minimum degree at least $ (1- |F|^{-4}) n$ has an $F$-decomposition. Our main contribution is a general method which turns an approximate decomposition into an exact one.
This is joint work with Ben Barber, Daniela Kühn and Deryk Osthus.
Friday 15 May - Ryan Martin (Iowa State University)
Recent progress on diamond-free families
In the Boolean lattice, a diamond is a subposet of four distinct subsets A, B, C, D such that A ⊂ B, C and D ⊃ B, C. One of the most well-studied problems in extremal poset theory is determining the size of the largest diamond-free family in the n-dimensional Boolean lattice. We will discuss some recent progress on this problem.
Thursday 7 May - Aytek Erdil (Cambridge)
Two-sided Matching With Ties
Much of the two-sided matching literature maintains the assumption that agents are not indifferent between any two members of the opposite side. Various real life applications, however, require the market designer to deal with ties carefully. In the presence of ties, stability no longer implies Pareto efficiency, and the deferred acceptance algorithm can not be applied to produce a Pareto efficient or a worker/firm optimal stable matching.
We allow ties in preference rankings and show that the Pareto dominance relation on stable matchings can be captured by two simple operations which are stability preserving reshuffling of workers and firms via cycles or chains. Likewise, the two relations defined via workers' welfare and firms' welfare can also be broken down to two similar procedures. These results establish a neat structure for the set of stable matchings, and lead to fast algorithms to compute a Pareto efficient and stable matching, and a worker optimal stable matching.
Thursday 30 April - Rahul Savani (Liverpool)
The Complexity of the Simplex Method
The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE -complete to find the solution that is computed by the simplex method using Dantzig’s pivot rule. Secondly, we prove that deciding whether Dantzig’s rule ever chooses a specific variable to enter the basis is PSPACE -complete. We use the known connection between Markov decision processes (MDPs) and linear programming, and an equivalence between Dantzig’s pivot rule and a natural variant of policy iteration for average-reward MDPs. We construct MDPs and show PSPACE -completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.
Joint work with John Fearnley.
Thursday 19 March - Elias Koutsoupias (Oxford)
A primer on Principal/Agent models and their recent extensions
We develop a general duality-theory framework for revenue maximization in additive Bayesian auctions which generalises the virtual values of Myerson. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. We give optimal auctions for a large class of distributions for two items in the monopoly setting, and we resolve the case of the uniform distribution for up to six items. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal mechanism itself.
Thursday 12 March - Yannai Gonczarowski (HUJI and MSR)
Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games
Drawing intuition from a (physical) hydraulic system, we present a novel framework, constructively showing the existence of a strong Nash equilibrium in resource selection games (i.e. asymmetric singleton congestion games) with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the invariance of the cost of each given resource across all Nash equilibria. Our proofs allow for explicit calculation of Nash equilibrium and for explicit and direct calculation of the resulting (invariant) costs of resources, and do not hinge on any fixed-point theorem, on the Minimax theorem or any equivalent result, on the existence of a potential, or on linear programming. A generalization of resource selection games, called resource selection games with I.D.-dependent weighting, is defined, and the results are extended to this family, showing that while resource costs are no longer invariant across Nash equilibria in games of this family, they are nonetheless invariant across all strong Nash equilibria, drawing a novel fundamental connection between group deviation and I.D.-congestion. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described.
Joint work with Moshe Tennenholtz.
Thursday 5 March - Will Perkins (Birmingham)
Algorithmic Partitioning of Random Hypergraphs
Consider a random hypergraph formed by fixing a bipartition of the vertex set and adding k-uniform hyperedges independently at random with probabilities that depend on how the edges cross the partition.
This general model includes both the stochastic block model (k=2) and planted random k-SAT, and arises in cryptography and the analysis of clustering algorithms. Depending on the distribution of hyperedges and their density, the computational problem of recovering the partition can be tractable or intractable. I will present new results identifying the algorithmic tractability threshold for a large class of algorithms. Based on joint work with Vitaly Feldman and Santosh Vempala.
Thursday 26 February - Karen Gunderson (Bristol)
Bootstrap percolation on infinite trees
A bootstrap process is a type of cellular automaton with vertices of a graph in one of two states: `healthy' or `infected'. For any positive integer $r$, the $r$-neighbour bootstrap process is the following update rule for the states of vertices: infected vertices remain infected forever and each healthy vertex with at least $r$ infected neighbours becomes itself infected. These updates occur simultaneously and are repeated at discrete time intervals. Percolation is said to occur if all vertices are eventually infected.
Of interest is the random case, where each vertex is infected independently with a fixed probability $p$. For an infinite graph, one would like to know the values of $p$ for which the probability of percolation is positive. I will give some of the history of this problem for regular trees and present some new results for bootstrap percolation on certain classes of randomly generated trees: Galton--Watson trees.
Thursday 19 February - Jaehoon Kim (Birmingham)
Uniform hypergraphs with no $r$-regular subgraphs
An $n$-vertex graph with no $r$-regular subgraphs are forests if $r=2$, thus it has at most $n-1$ edges. For $r>=3$, Pyber showed that it has at most $O(n log(n))$ edges. For hypergraphs, Mubayi and Verstraete showed that $n$-vertex $k$-graphs with no $2$-regular subgraphs has at most ${{n-1} choose {k-1}}$ edges if $k>=4$ is even and $n$ is sufficiently large. In this talk, we prove that for every integer $r>=3$, an $n$-vertex $k$-graph $H$ containing no $r$-regular subgraphs has at most $(1+o(1)){{n-1} choose {k-1}}$ edges if $k>r$ and $n$ is sufficiently large. Moreover, if $r=3,4, r|k$, and $n$, $k$ are both sufficiently large, then the maximum number of edges in H is exactly ${{n-1} choose {k-1}}$, with equality only if all edges contain a specific vertex $v$. We also ask some related questions.
Thursday 12 February - Yuri Rabinovich (University of Haifa)
Three Extremal Problems in Combinatorial Theory of Simplicial Complexes
Simplicial complexes are, on one hand, a natural higher-dimensional analogue of graphs, and on the other hand, a basic object and tool in Topology. They are akin to hypergraphs, but posses precious additional structure resulting from the presence of the boundary operator. Surprisingly, despite some brilliant but isolated applications, the combinatorics of simplicial complexes has been, up until recently, relatively little studied.
We have chosen the following three extremal problems to introduce the basic objects of study, and to exhibit some of their structure:
-
How large can be a simple d-cycle on [n]? In particular, are there "Hamiltonian" d-cycles?
-
How large can be a simple co-cycle in [n]?
-
What is the smallest degree of all (d-1)-faces of d-complex, ensuring that it contains a hypertree in [n]?
Based on joint work with R. Deepak, N. Linial, R. Matthews, I.Newman and Y.Peled.
Thursday 5 February - Maya Stein (U Chile)
Monochromatic path/cycle partitions
A conjecture of Gyárfás says that given any colouring with $r$ colours of the edges of the complete graph K_n on n vertices, there are r disjoint monochromatic paths that induce a partition of V(K_n). The conjecture is true for r >= 3. Replacing paths with cycles, it is known that in general, the number of cycles needed is greater than r, but can be bounded by a function of r. (Here, single vertices/edges count as cycles.) For r=2, it is known that 2 paths/cycles suffice.
This talk gives an overview on the history of the problem. We then describe some recent results for bipartite and multipartite graphs, with fixed values of r. We also study variants of the problem for r-local colourings. The talk is based on results that are joint work with Conlon, with Lang, with Lang and Schaudt, and with Schaudt, respectively.
Thursday 29 January - Ping Hu (Warwick)
Rainbow triangles in three-colored graphs
Erdős and Sós proposed a problem of determi vv ning the maximum number F(n) of rainbow triangles in 3-edge-colored complete graphs on n vertices.
They conjectured that F(n)=F(a)+F(b)+F(c)+F(d)+abc+abd+acd+bcd, where a+b+c+d=n and a,b,c,d are as equal as possible.
We prove that the conjectured recurrence holds for sufficiently large n. We also prove the conjecture for n = 4^k for all k >= 0. These results imply that lim F(n)/{n choose 3}=0.4, and determine the unique limit object. In the proof we use flag algebras combined with stability arguments.
Joint work with József Balogh, Bernard Lidický, Florian Pfender, Jan Volec and Michael Young.
Thursday 22 January - Andrei Kupavskii (EPFL)
Number of double-normals in a set of n points in space
Two points p,q in a subset S of R^d form a double-normal, if S lies between two parallel hyperplanes passing through p and q and that are orthogonal to pq. We refine the results on the number of double-normals in an n-point set in R^d that are due to J. Pach and K. Swanepoel. The problem appears to be closely connected with the P. Erdos' problem on the number of points in R^d that form only non-obtuse angles.