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 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