# 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 the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk

Upcoming Speakers:

Friday 04 October - Natalie Behague (QMUL)
Venue: 32L.B.09 from 12:00 - 13:00

Title and abstract TBC.

## Previous seminars in this series:

Summer Term 2019

Friday 31 May - Christoph Spiegel (UPC)
Venue: 32L.B.09 from 12:00 - 13:00

Intervals in the Hales-Jewett Theorem
The Hales–Jewett Theorem states that any r–colouring of [m]^n contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.

Friday 10 May - Gwen McKinley (MIT)

Super-logarithmic cliques in dense inhomogeneous random graphs

In the theory of dense graph limits, a graphon is a symmetric measurable function $W\colon[0,1]^2\to [0,1]$. Each graphon gives rise naturally to a random graph distribution, denoted $\mathbb{G}(n,W)$, that can be viewed as a generalization of the Erd\H{o}s-R\'enyi random graph. Recently, Dole{\v{z}}al, Hladk{\'y}, and M{\'a}th{\'e} gave an asymptotic formula of order $\log n$ for the clique number of $\mathbb{G}(n,W)$ when $W$ is bounded away from 0 and 1. We show that if $W$ is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of $\mathbb{G}(n,W)$ will be $\Theta(\sqrt{n})$ almost surely. We also give a family of examples with clique number $\Theta(n^\alpha)$ for any $\alpha\in(0,1)$, and some conditions under which the clique number of $\mathbb{G}(n,W)$ will be $o(\sqrt{n})$, $\omega(\sqrt{n}),$ or $\Omega(n^\alpha)$ for $\alpha\in(0,1)$.

Lent Term 2019

Friday 22 March - Alberto Espuny Diaz (University of Birmingham)

Resilient degree sequences with respect to Hamiltonicity in random graphs
The local resilience of a graph with respect to a property P can be defined as the maximum number of edges incident to each vertex that an adversary can delete without destroying P. The resilience of random graphs with respect to various properties has received much attention in recent years, with a special emphasis on Hamiltonicity. Based on different sufficient degree conditions for Hamiltonicity, we investigate a notion of local resilience in which the adversary is allowed to delete a different number of edges at each vertex, and obtain some results which improve on previous results. This is joint work with P. Condon, J. Kim, D. Kühn and D. Osthus.

Friday 22 February - Bernhard von Stengel (LSE)

Computational progress on the Catch-Up game
We report on computational progress on the game "Catch-Up" analyzed by Isaksen, Ismail, Brams, and Nealen in 2015. Two players pick and remove numbers from the set {1,...,n} according to the "catch-up" rule that says you pick the next number as long as the sum of your numbers is less than that of the other player. After that (having reached an equal or higher sum), players switch. The player with the higher sum at the end wins. For n=5, for example, the first player wins by first picking 3. With old-fashioned memory-saving coding but large computer memory of a standard modern laptop (8 GByte RAM, 37 GByte virtual memory, 28 hours computation time), we extend the computational analysis for optimal play from maximally n=20 to n=34. The following pattern emerges: When there can be a draw (when n or n+1 is divisible by 4), there will be a draw, and when there cannot be a draw, then for n=21 or larger the first player wins with the first picked number no larger than 3. (For n = 9,10,14,18 the first player loses, which seem to be the exceptions.) We prove that if there is a first winning move then it is unique. Further computational analysis may help in eventually finding an induction proof to prove this in general, which is challenging.

Friday 15 February - Dennis Clemens (TUHH)

On minimal Ramsey graphs and Ramsey equivalence for multiple colours.
For an integer $q\geq 2$, we call $G$ a $q$-Ramsey-minimal graph for $H$ if every $q$-edge-colouring of $G$ contains a monochromatic copy of $H$, but no proper subgraph of $G$ has this property. Utilising the method of signal senders and generalising so-called indicators to multiple colours, we prove that if $2\leq r< q$ and $G$ is an $r$-Ramsey-minimal graph for $H$ then $G$ is contained in an infinite number of $q$-Ramsey-minimal graphs for $H$, provided that $H$ is $3$-connected. As a consequence we can show that the collection $\{M_q(H) : H \text{ is 3-connected}\}$ forms an antichain, where $M_q(H)$ denotes the set of all graphs that are $q$-Ramsey-minimal for $H$. Moreover, call $H_1$ and $H_2$ $q$-equivalent if $M_q(H_1)=M_q(H_2)$ holds. We generalize previous results by Bloom and Liebenau as well as Fox, Grinshpun, Liebenau, Person and Szab\'o regarding the class of graphs that are $q$-equivalent to the complete graph $K_k$. Joint work with Damian Reding and Anita Liebenau.

Friday 8 February - Attila Dankovics (LSE)

Low independence number and Hamiltonicity implies pancyclicity
Given a Hamiltonian graph $G$ with independence number at most $k$ we are looking for the minimum number of vertices $f(k)$ that guarantees that $G$ is pancyclic. The problem of finding $f(k)$ was raised by Erdős who showed that $f(k)\le 4k^4$, and conjectured that $f(k)=\Theta(k^2)$. Formerly the best known upper bound was $f(k)=O(k^{7/3})$ by Lee and Sudakov. We improve this bound and show that $f(k)=O(k^{11/5})$.

Friday 25 January - Cedric Koh (LSE)

An Efficient Characterization of Submodular Spanning Tree Games
Cooperative games are an important class of problems in game theory, where the goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing some of the most important solution concepts proposed in the literature. For this reason, a relevant question is whether one can give a polynomial time characterization of submodular instances, for prominent cooperative games that are in general non-convex.

In this talk, we focus on a fundamental and widely studied cooperative game, namely the spanning tree game. An efficient recognition of submodular instances of this game was not known so far, and explicitly mentioned as an open question in the literature. We here settle this open problem by giving a polynomial time characterization of submodular spanning tree games.

This is joint work with Laura Sanità.

Michaelmas Term 2018

Friday 14 December - Bento Natura (LSE)

The Shallow-Light Steiner Tree Problem
In a central step in the design of modern VLSI-chips, millions of pins have to be connected. The scale of this task requires fast algorithms with provably good performance.

The problem can be approximated by the Shallow-Light Steiner Arborescence problem, in which we minimize the total length of a Steiner Arborescence that propagates a signal from a source s to a set of sinks T, such that the delay on the paths obeys given constraints. In our model, the delay depends on the length of the path as well as on the number of edges on the path.

We present algorithms and inapproximability results for the general case and based on this a quasilinear time algorithm with improved approximation guarantee for the special case, where the metric space is (R^2, l^1).

Friday 30 November - Benny Sudakov (ETH)

Subgraph statistics
Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given a large graph $G$, what is the fraction of $k$-vertex subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or complete, and $\ell$ is zero or $\binom k 2$, this fraction can be exactly 1. On the other hand if $\ell$ is not one these extreme values, then by Ramsey's theorem, this fraction is strictly smaller than 1.

The systematic study of the above question was recently initiated by Alon, Hefetz, Krivelevich and Tyomkyn who proposed several natural conjectures. In this talk we discuss a theorem which proves one of their conjectures and implies an 0asymptotic version of another.  We also make some first steps towards analogous question for hypergraphs. Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities and hypercontractivity.

Joint work with M. Kwan and T. Tran

Convex Ramsey property and non-amenability of automorphism groups of generic structures
In this talk we start by presenting some correspondences between (extreme) amenability of automorphism groups of Fraïssé–Hrushovski generic structures, and Ramsey type properties of their smooth classes, similar to results of Kechris, Pestov and Todorcevic (2005), and Moore (2013). Then we focus on the combinatorial part and especially on the convex Ramsey property. The convex Ramsey property can be translated to some conditions on matrices. We will then consider automorphism groups of certain Hrushovski's generic graphs and show that they are not amenable using certain matrices by exhibiting a combinatorial/geometrical criterion which forbids amenability.

Friday 16 November - Rachel Kirsch (LSE)

Many cliques with few edges
The problem of maximizing the number of cliques has been studied within several classes of graphs. For example, among graphs on $n$ vertices with clique number at most $r$, the Tur\'an graph $T_r(n)$ maximizes the number of copies of $K_t$ for each size $t$. Among graphs on $m$ edges, the colex graph $\mathcal{C}(m)$ maximizes the number of $K_t$'s for each size $t$.

In recent years, much progress has been made on the problem of maximizing the number of cliques among graphs with $n$ vertices and maximum degree at most $r$. The graph $aK_{r+1}\cup K_b$, where $n = a(r+1)+b$ and $0 \le b \le r$, was shown to maximize the total number of cliques, and is conjectured to maximize the number of $K_t$'s for $t \ge 3$. This conjecture has been proven in significant cases.

In this talk, we discuss the edge analogue of this problem: which graphs with $m$ edges and maximum degree at most $r$ have the maximum number of cliques? We prove in some cases that the extremal graphs again contain as many disjoint copies of $K_{r+1}$ as can fit, with the leftovers in another component. In the edge analogue, these remaining edges form a colex graph.

Convex Ramsey property and non-amenability of automorphism groups of generic structures
In this talk we start by presenting some correspondences between (extreme) amenability of automorphism groups of Fraïssé–Hrushovski generic structures, and Ramsey type properties of their smooth classes, similar to results of Kechris, Pestov and Todorcevic (2005), and Moore (2013). Then we focus on the combinatorial part and especially on the convex Ramsey property. The convex Ramsey property can be translated to some conditions on matrices. We will then consider automorphism groups of certain Hrushovski's generic graphs and show that they are not amenable using certain matrices by exhibiting a combinatorial/geometrical criterion which forbids amenability

Friday 12 October - Patrick Morris (FU Berlin)
Venue: 32L.B.09 from 12:00 - 13:00

Finding any given 2-factor in sparse pseudorandom graphs
Given an $n$-vertex pseudorandom graph $G$ and a potential 2-factor $H$ (that is, a union of disjoint cycles whose lengths sum to $n$), we wish to find a copy of $H$ in $G$, i.e.\ an embedding $\varphi\colon V(H)\to V(G)$ so that $\varphi(u)\varphi(v)\in E(G)$ for all $uv\in E(H)$. Particular instances of this problem include finding a triangle-factor and finding a Hamilton cycle in $G$.

In this talk, after giving the relevant context and history in this field, we will sketch how to find a given $H$ in any suitably pseudorandom graph $G$. The graphs we will consider will be $(n,d,\lambda)$ graphs i.e. n vertex d-regular graphs whose second eigenvalue in absolute value is $\lambda$.

Our condition $\lambda=O(d^2/(n\log n))$ is within a log factor from being tight and provides a positive answer to a recent question of Nenadov (arXiv:1805.09710).

This represents joint work with Jie Han, Yoshiharu Kohayakawa and Yury Person.

Friday 5 October - Matthew Jenssen (University of Oxford)

Kissing Numbers and Spherical Codes in High Dimension
We prove a lower bound of $\Omega (d^{3/2}\cdot(2/\sqrt{3})^d)$ on the kissing number in dimension $d$. This improves the classical lower bound of Chabauty, Shannon, and Wyner by a linear factor in the dimension.  We obtain a similar linear factor improvement to the best known lower bound on the maximal size of a spherical code of acute angle $\theta$ in high dimensions.

Joint work with Felix Joos and Will Perkins.

20182017, 2016, 2015, 2014, 2013, 2012