Below you can find information about past seminars in this series from 2014. The seminars are listed in reverse chronological order, most recent first.
Friday 21 November - Diana Piguet| (Pilsen)
Embedding cycles of given length in oriented graphs
Kelly, Kuehn and Osthus conjectured that for any length L>3 and the smallest number k>2 that does not divide L, any large enough oriented graph G with minimum semidegree at least |V(G)|/k+1 contains a directed cycle of length L. I shall present an approximate solution of this conjecture for the case when L is large enough compared to k and k>3. The case when k=3 was already settled by Kelly, Kuehn and Osthus.
This is a joint work with Daniela Kuehn and Deryk Osthus.
Friday 14 November - Frank Mousset| (ETH Zurich)
Packing a randomly edge-coloured graph with rainbow k-outs
Let G be a graph on n vertices and let k,c be fixed positive integers. The random subgraph G_k of G is obtained by letting each vertex of G pick k neighbours uniformly at random from its neighbourhood in G ("k-out"). On the other hand, the edge-coloured random subgraph G(p,c) is obtained by keeping each edge independently with probability p, and then colouring each edge randomly with a color from the set {1,...,c}.
We show that if p >> log n/delta(G), then in a typical H ~ G(p,kn), one can find t = (1-o(1)) delta(G)p/(2k) edge-disjoint subgraphs H_i, with the following properties:
(a) each H_i is almost distributed like G_k, in the sense that monotone properties of G_k transfer to H_i;
(b) each H_i is rainbow, i.e., each edge is painted in a different colour.
Since the typical G_k has kn edges (average degree 2k), and since the average degree of G(p,kn) is delta(G)p, this result is asymptotically optimal.
Immediate applications of this result are rainbow packing problems in G(p,c). For example, it follows that if p >> log n/n, the typical H ~ K_n(p,23n) contains (1-o(1)) np/46 edge-disjoint rainbow Hamilton cycles. Another example: if G has minimum degree (1+eps) n/2, then there exist c=O(n) and t=O(np) such that G(p,c) (for p >> log n/n) contains t edge-disjoint rainbow Hamilton cycles. Although these results are far from optimal, their proofs are extremely easy.
Friday 7 November - Frank Page| (Indiana University Bloomington)
Parameterized Games and K-Correspondences
For a large class of nonatomic, parametrized games, including all nonatomic discounted stochastic games of the type studied by Nowak and Raghavan (1992), we show that each game in the class has a Nash payoff correspondence that is a K-correspondence - or equivalently, is a correspondence having the K-limit property. We then show that if a Nash payoff correspondence has the K-limit property, then its induced Nash payoff selection correspondence is approximable in the weak star topology and therefore has fixed points.
Our results lead directly to the resolution of a long-standing open problem in the theory of discounted stochastic games (see Page, 2014).
PDF of abstract|
This is joint work with Jieshuang He (Indiana University Bloomington)
Friday 24 October - Benny Sudakov| (ETH Zurich)
Grid Ramsey problem and related questions
The Hales-Jewett theorem is one of the pillars of Ramsey theory, from which many other results follow.
A celebrated result of Shelah says that Hales-Jewett numbers are primitive recursive. A key tool used in his proof, known as the cube lemma, has become famous in its own right. In its simplest form, it says that if we color the edges of the Cartesian product $K_n \times K_n$ in $r$ colors then, for $n$ sufficiently large, there is a rectangle with both pairs of opposite edges receiving the same color.
Hoping to improve Shelah's result, Graham, Rothschild and Spencer asked more than 20 years ago whether the cube lemma holds with $n$ which is polynomial in $r$. We show that this is not possible by providing a superpolynomial lower bound in $r$. We also discuss a number of related questions, among them a solution of a problem of Erdos and Gyarfas on generalized Ramsey numbers.
This is joint work with Conlon, Fox and Lee.
Friday 4 July
Nicola Wittur (LSE)
Shapley Value on Convex Geometries
A central question in cooperative game theory is the problem of a "fair" allocation of the value that has been generated by a coalition of players among the individual players. The Shapley value is one of the most common allocation rules studied so far. It is based on the assumption that every subset of players is a feasible coalition. There have been attempts to analyze situations (and the corresponding Shapley value) in the case of restricted cooperation possibilities. Based on a paper by Bilbao and Edelman, we will present the case in which the feasible coalitions form a convex geometry: we will introduce their main findings and will point at some drawbacks of their approach.
Friday 20 June
Andrzej Rucinski |(Poznan)
Exponential bounds for Folkmann numbers
Abstract: Not available
Friday 21 March
Julia Ehrenmueller| (TU Hamburg-Harburg)
Almost acyclic avoider-enforcer games
In this talk we consider biased (1:b) Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if b \geq 200 n \ln n. By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non-k-colorability game, and the K_t-minor game. Moreover, we give a slight improvement for the lower bound in the non-planarity game.
This is joint work with Dennis Clemens, Yury Person, and Tuan Tran
Friday 14 March
Yury Person| (Goethe-Universität, Frankfurt)
Minimum degree of minimal Ramsey graphs for multiple colors
A graph $G$ is called $H$-Ramsey if no matter how one colors its edges red/blue, there is a monochromatic copy of $H$.
We say that $G$ is minimal $H$-Ramsey if $G$ is $H$-Ramsey, but no proper graph of it is. Burr, Erd\H{o}s and Lovász studied minimum degree among all minimal $K_t$-Ramsey graphs and showed that it equals $(t-1)^2$. We discuss generalizations of their result to more colors.
Joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau and Tibor Szabó.
Friday 7 March
Daniel Quiroz (LSE)
Generalized coloring numbers.
Based on a paper of Kierstead and Yang (Orderings on Graphs and Game Coloring Number, 2003) generalized coloring numbers will be presented. The existence of upper bounds for the k-coloring number will be discussed for the case of planar graphs, together with some applications.
Friday 28 February
Jozsef Balogh| (University of Illinois & University of Szeged)
Subdivisions of a large clique in $C_6$-free graphs
Mader conjectured that every $C_4$-free graph has a subdivision of a clique of order linear in its average degree. We show that every $C_6$-free graph has such a subdivision of a large clique.
We also prove the dense case of Mader's conjecture in a stronger sense, i.e.for every $c$, there is a $c'$ such that every $C_4$-free graph with average degree $cn^{1/2}$ has a subdivision of a clique $K_\ell$ with $\ell=\lfloor c'n^{1/2}\rfloor$ where every edge is subdivided exactly $3$ times.
This is joint work with Hong Liu and Maryam Sharifzadeh.
This lecture forms part of the Discrete Mathematics and Game Theory Seminar |
Friday 21 February
Alexey Pokrovskiy (FU Berlin)
Graphs with 2|G|-2 edges
We discuss graphs on n vertices which have 2n-2 edges and no proper induced subgraphs of minimum degree 3. Erdős, Faudree, Gyárfás, and Schelp conjectured that such graphs always have cycles of lengths 3,4,5,...,C(n) for some increasing function C(n). We'll talk about a disproof this conjecture. We'll also discuss a related problem about possible leaf to leaf path lengths in trees.
This is joint work with Narins and Szabó.
Friday 14 February
Ron Peretz |(LSE)
Tutorial: Blackwell's Approachability Theorem
Friday 24 January
Matthew Jenssen (LSE)
Minimum degree Turán problems
Turán problems concern the maximum number of edges in an F-free r-graph, but it is also natural to ask about the maximum possible minimum degree. More precisely, for an r-graph G and 0\leq s \leq r-1 let \delta_s(G) be the minimum over all sets S of s vertices of the number of edges containing S. We can then define a generalised Turán number ex_s(n,F) as the largest value of \delta_s(G) attained by an F-free r-graph G on n vertices. We will discuss recent developments in the study of such Turán numbers and establish the best known asymptotic lower bound for ex_2(n,K_4^3)/n.
Friday 17 January
Zibo Xu| (Stockholm School of Economics)
Title and abstract not available