PhD Seminar on Combinatorics, Games and Optimisation

Below you'll find the program for the PhD Seminar on Combinatorics, Games and Optimisation (formerly known as the Lunchtime Seminar: 2006-2016). The Seminar normally takes place on Fridays from 12.00 - 13:00 in room 32L.B.09 (32 Lincoln's Inn Fields, LSE).

Questions, suggestions, etc., about the seminar can be forwarded to Enfale Farooq, the Research Manager, on

Upcoming Speakers:

Friday 15 November - Cosmin Pohoata (Caltech)
Venue: 32L.B.09 from 12:00 - 13:00

Sets without 4APs but with many 3APs
It is a classical theorem of Roth that every dense subset of $\left\{1,\ldots,N\right\}$ contains a nontrivial three-term arithmetic progression. Quantitatively, results of Sanders, Bloom, and Bloom-Sisask tell us that subsets of relative density at least $1/(\log N)^{1-\epsilon}$ already have this property. In this talk, we will discuss about some sets of $N$ integers which unlike $\left\{1,\ldots,N\right\}$ do not contain nontrivial four-term arithmetic progressions, but which still have the property that all of their subsets of relative density at least $1/(\log N)^{1-\epsilon}$ must contain a three-term arithmetic progression. Perhaps a bit surprisingly, these sets turn out not to have as many three-term progressions as one might be inclined to guess, so we will also address the question of how many three-term progressions can a four-term progression free set may have. Finally, we will also discuss about some related results over $\mathbb{F}_{q}^n$. Based on joint works with Jacob Fox and Oliver Roche-Newton.

Wednesday 20 November - Franziska Eberle (Universität Bremen)
Venue: 32L.LG.14 from 15:30 - 17:00
**change of day, venue and time**

Title and abstract TBC

Friday 22 November - Nora Frankl (LSE)
Venue: 32L.B.09 from 12:00 - 13:00

Title and abstract TBC

Friday 6 December - Bento Natura (LSE)
Venue: 32L.B.09 from 12:00 - 13:00

Title and abstract TBC

Previous seminars in this series: 

Michaelmas Term

Friday 8 November - Olaf Parczyk (LSE)

The size-Ramsey number of tight 3-uniform paths
Given a hypergraph H, the size-Ramsey number is the smallest integer m such that there exists a graph G with m edges with the property that in any colouring of the edges of G with two colours there is a monochromatic copy of H. Extending on results for graphs we prove that the size Ramsey number of the 3-uniform tight path on n vertices is linear in n.

This is joint work with Jie Han, Yoshiharu Kohayakawa, and Guilherme Mota.

Friday 18 October - Oliver Janzer (University of Cambridge)

The extremal number of subdivisions
For a graph H, the extremal number ex(n,H) is defined to be the maximal number of edges in an H-free graph on n vertices. For bipartite graphs H, determining the order of magnitude of ex(n,H) is notoriously difficult. In this talk I present recent progress on this problem. 
The k-subdivision of a graph F is obtained by replacing the edges of F with internally vertex-disjoint paths of length k+1. Most of our results concern the extremal number of various subdivided graphs, especially the subdivisions of the complete graph and the complete bipartite graph. 

Partially joint work with David Conlon and Joonkyung Lee.

Friday 4 October - Natalie Behague (QMUL)

Semi-perfect 1-factorizations of the Hypercube
A 1-factorization of a graph H is a partition of the edges of H into disjoint perfect matchings {M_1 , M_2 , . . . , M_n}, also known as 1-factors. A 1-factorization M = {M_1 , M_2 , . . . , M_n} of a graph G is called perfect if the union of any pair of distinct 1-factors M_i , M_j is a Hamilton cycle. The existence or non-existence of perfect 1-factorizations has been studied for various families of graphs. Perhaps the most famous open problem in the area is Kotzig’s conjecture, which states that the complete graph K_2n has a perfect 1-factorization. In this talk we shall focus on another well-studied family of graphs: the hypercubes Q_d in d dimensions. There is no perfect 1-factorization of Q_d for d > 2. As a result, we need to consider a weaker concept.
A 1-factorization M is called k-semi-perfect if the union of any pair of 1-factors M_i , M_j with 1 ≤ i ≤ k and k + 1 ≤ j ≤ n is a Hamilton cycle. It was proved that there is a 1-semi-perfect 1-factorization of Q_d for every integer d ≥ 2 by Gochev and Gotchev, Královič and Královič, and Chitra and Muthusamy, in answer to a conjecture of Craft. My main result is a proof that there is a k-semi-perfect 1-factorization of Q_d for all k and all d, except for one possible exception when k = 3 and d = 6. I will sketch the proof and explain why this is, in some sense, best possible. I will conclude with some questions concerning other generalisations of perfect 1-factorizations.

201920182017, 2016, 2015, 2014, 2013, 2012