Home > Department of Mathematics > Seminars > Seminar on Combinatorics, Games and Optimisation
How to contact us

Department of Mathematics
Columbia House
London School of Economics
Houghton Street
London WC2A 2AE, UK

 

Email: maths.info@lse.ac.uk
Tel: +44(0)207 955 7732/7925
Follow us on Twitter: Twitter
Read our research blog:  http://blogs.lse.ac.uk/maths/
Connect with us on LinkedIn: LinkedIn
Watch our videos on YouTube: Icon of the YouTube logo

 

Click here for information on how to get to LSE using public transport and maps of the campus

Seminar on Combinatorics, Games and Optimisation

Below you'll find the programme for the Seminar on Combinatorics, Games and Optimisation (a joining together of the former Seminar on Discrete Mathematics and Game Theory and the former Seminar on Operations Research).

This semianr series covers many of the research areas in the Department: discrete mathematics, algorithms, game theory and operational research.

Unless stated below, this Seminar normally takes place:

Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk.

Upcoming Speakers:

MICHAELMAS TERM

Wednesday 18 October - no seminar

Thursday 19 October - no seminar

Wednesday 25 October - 15.30 - 32L.LG.14, 32 Lincoln's Inn Fields, LSE
Péter Pál Pach (Warwick/Technical University Budapest)
On some recent applications of the polynomial method

In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z_4^n and F_q^n are exponentially small (compared to the size of the group). Since then many interesting applications of this method were shown, for instance, the solution of the Erdős-Szemerédi sunflower conjecture, tight bound for Green’s arithmetic triangle removal lemma and growth rate of tri-colored sumfree sets. Finally, I will also mention some open problems.

Thursday 26 October - 14.00 - CLM.7.03, Clement House, LSE
He Sun (Edinburgh)
Heat kernels in graphs: A journey from random walks to geometry, and back

Heat kernels are one of the most fundamental concepts in physics and mathematics. In physics, the heat kernel is a fundamental solution of the heat equation and connects the Laplacian operator to the rate of heat dissipation. In spectral geometry, many fundamental techniques are based on heat kernels. In finite Markov chain theory, heat kernels correspond to continuous-time random walks and constitute one of the most powerful techniques in estimating the mixing time. In this talk, we will briefly discuss this line of research and its relation to heat kernels in graphs. In particular, we will see how heat kernels are used to design the first nearly-linear time algorithm for finding clusters in real-world graphs. Some interesting open questions will be addressed in the end.

Wednesday 1 November - 15.30 - 32L.LG.14, 32 Lincoln's Inn Fields, LSE
Peter Csikvari (Budapest)
Schrijver's theorem on the number of perfect matchings and its variants

In this talk we will sketch a new proof of Schrijver's theorem. This theorem asserts that a d-regular bipartite graph on 2n vertices has at least C_d^n perfect matchings, where C_d=(d-1)^(d-1)/d^(d-2). (I will explain where the constant comes from.) The new proof uses ideas from graph limit theory, and relies on the work of Heilmann and Lieb concerning the matching polynomial. Then we will survey several further applications of the method.

Thursday 2 November - 14.00 - CLM.7.03, Clement House, LSE
Liana Yepremyan (Oxford)
Title and abstract TBC

Wednesday 8 November - 15.30 - 32L.LG.14, 32 Lincoln's Inn Fields, LSE
Speaker, title and abstract TBC

Thursday 9 November - 14.00 - CLM.7.03, Clement House, LSE
Christoph Koch (Warwick)
Title and abstract TBC

Wednesday 15 November - 15.30 - 32L.LG.14, 32 Lincoln's Inn Fields, LSE
Sergei Chubanov (Siegen)
A polynomial scaling algorithm for linear programming

In this talk we will consider a polynomial algorithm for linear programming based on a scaling technique. As well as the ellipsoid method, this algorithm is applicable to linear problems given by separation oracles. We will also discuss some numerical results concerning machine learning applications and the perspectives of this algorithm in infinite-dimensional linear optimization.

Thursday 16 November - 14.00 - CLM.7.03, Clement House, LSE
Tim Roughgarden (Stanford & LSE)
Title and abstract TBC

Wednesday 22 November - 15.30 - 32L.LG.14, 32 Lincoln's Inn Fields, LSE
Speaker, title and abstract TBC

Thursday 23 November - 14.00 - CLM.7.03, Clement House, LSE
Speaker, title and abstract TBC

Wednesday 29 November - 15.30 - 32L.LG.14, 32 Lincoln's Inn Fields, LSE
Speaker, title and abstract TBC

Thursday 30 November - 14.00 - CLM.7.03, Clement House, LSE
Speaker, title and abstract TBC

Wednesday 6 December - no seminar

Thursday 7 December- 14.00 - CLM.7.03, Clement House, LSE
Speaker, title and abstract TBC

Previous seminars in this series: 20172016

Seminar on Discrete Mathematics and Game Theory: 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004 and before

Seminar on Operations Research: 2016, September 2015 - December 2015, August 2014 - August 2015, October 2010 - July 2014

 

Share:Facebook|Twitter|LinkedIn|