BannerDM1400x300

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 E.Farooq@lse.ac.uk

Upcoming Speakers:

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

A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Abstract TBC

Friday 13 December - Gal Kronenberg (University of Oxford)
Venue: 32L.B.09 from 12:00 - 13:00


Title and abstract TBC

Previous seminars in this series: 

Michaelmas Term

Friday 22 November - Nora Frankl (LSE)

On the number of discrete chains in the plane
Determining the maximum number of unit distances that can be spanned by n points in the plane is a difficult problem, which is wide open. The following more general question was recently considered by Eyvindur Ari Palsson, Steven Senger, and Adam Sheffer.  For given distances t_1,...,t_k a (k+1)-tuple (p_1,...,p_{k+1}) is called a k-chain if ||x_i-x_{i+1}||=t_i for i=1,...,k. What is the maximum possible number of k-chains that can be spanned by a set of n points in the plane? Improving the result of Palsson, Senger and Sheffer, we determine this maximum up to a small error term (which, for k=1 mod 3 involves the maximum number of unit distances). We also consider some generalisations, and the analogous question in R^3. Joint work with Andrey Kupvaskii.

Wednesday 20 November - Franziska Eberle (Universität Bremen)

Commitment in online scheduling made easy
We study a fundamental online job admission problem where jobs with processing times and deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-server schedule which maximizes the number of jobs that complete on time. To circumvent known impossibility results, we make a standard slackness assumption by which the feasible time window for scheduling a job is at least (1+epsilon) times its processing time, for some epsilon>0. We consider a variant of the online scheduling problem where the provider has to satisfy certain commitment requirements. These requirements arise, for example, in modern cloud-services, where customers do not want last-minute rejections of critical tasks and request an early-enough provider-side commitment to completing admitted jobs.

Our main contribution is an optimal algorithm for online job admission with commitment. When a provider must commit upon starting a job, our bound is O(1/epsilon). This is best possible as there is a lower bound of Omega(1/epsilon) for online admission even without commitment. If the commitment decisions must be made before a job's slack becomes less than a delta-fraction of its size, we prove a competitive ratio of O(epsilon/((epsilon - delta) delta)) for 0 <delta<epsilon. This result interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm does admit any bounded competitive ratio.

Friday 15 November - Cosmin Pohoata (Caltech)

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.

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