Upcoming events

26 Feb 2018Discrete Mathematics Seminar, KdVI / CWI  Amsterdam, NetherlandsTitle: A new approach to Sidorenko's conjecture

19 Feb – 4 Mar 2018Graphs and Randomness, IMPA  Rio de Janeiro, Brazil

26–30 Mar 2018Workshop on Graph limits  Janov, Czechia
Journal publications (see also arXiv)

Tight bounds on the coefficients of partition functions via stability
Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hardcore model and monomerdimer model are the independence and matching polynomials respectively.
We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions.
As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of $q$colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least $5$. 
Extremes of the internal energy of the Potts model on cubic graphsRandom Structures & Algorithms (to appear)
We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the antiferromagnetic Potts model on cubic graphs at every temperature and for all $q \ge 2$.
This immediately implies corresponding tight bounds on the antiferromagnetic Potts partition function. Taking the zerotemperature limit gives new results in extremal combinatorics: the number of $q$colorings of a $3$regular graph, for any $q \ge 2$, is maximized by a union of $K_{3,3}$'s.
This proves the $d=3$ case of a conjecture of Galvin and Tetali. 
On the average size of independent sets in trianglefree graphsProceedings of the American Mathematical Society 146 (2018), 111124
We prove an asymptotically tight lower bound on the expected size of an independent set in a trianglefree graph on $n$ vertices with maximum degree $d$ drawn uniformly at random, showing the average is at least $(1+o_d(1)) \frac{\log d}{d}n$. This gives an alternative proof of Shearer's upper bound on the Ramsey number $R(3,k)$. We then prove a lower bound on the total number of independent sets in such a graph which is asymptotically tight in the exponent. In both cases, tightness is exhibited by a random $d$regular graph.
Our results come from considering the hardcore model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $\lambda^{I}$, for a fugacity parameter $\lambda>0$. We prove a general lower bound on the occupancy fraction of the hardcore model on trianglefree graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $\lambda =O_d(1)$.
We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a trianglefree graph and give some consequences of these conjectures in Ramsey theory. 
Multicolour Ramsey numbers of paths and even cyclesEuropean Journal of Combinatorics 63 (2017), 124–133
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that the kcolour Ramsey number of both an $n$vertex path and, for even $n$, an $n$vertex cycle is between $(k1)n+o(n)$ and $kn+o(n)$.
The upper bound was recently improved by Sárközy who gave a stability version of the classical theorem of Erdős and Gallai on graphs containing no long cycles. Here we obtain the first improvement to the coefficient of the linear term in the upper bound by an absolute constant. 
Independent Sets, Matchings, and Occupancy FractionsJourrnal of the London Mathematical Society 96 (2017), 47–66
We give tight upper bounds on the logarithmic derivative of the independence and matching polynomials of any $d$regular graph.
For independent sets, this is a strengthening of a sequence of results of Kahn, Galvin and Tetali, and Zhao that a disjoint union of $K_{d,d}$'s maximizes the independence polynomial and total number of independent sets among all dregular graphs.
For matchings, the result implies that disjoint unions of $K_{d,d}$'s maximize the matching polynomial and total number of matchings, as well as proving the Asymptotic Upper Matching Conjecture of Friedland, Krop, Lundow, and Markström.
The proof uses an occupancy method: we show that the occupancy fraction in the hardcore model and the edge occupancy fraction in the monomerdimer model are maximized over all $d$regular graphs by $K_{d,d}$.
Conference publications

Tight bounds on the coefficients of partition functions via stability (extended abstract)Electronic Notes in Discrete Mathematics 61 (2017), 317–321
We show how to use the recentlydeveloped occupancy method and stability results that follow easily from the method to obtain extremal bounds on the individual coefficients of the partition functions over various classes of bounded degree graphs.

Counting in hypergraphs via regularity inheritance (extended abstract)Electronic Notes in Discrete Mathematics 49 (2015), 413–417
A new approach to the counting lemma in 3uniform hypergraphs. We develop a theory of regularity inheritance and use it to prove a slight strengthening of the counting lemma of Frankl and Rödl. Full paper to follow.
Other publications

Extremal and probabilistic results for regular graphsPhD Thesis, The London School of Economics and Political Science (2017)
In this thesis we explore extremal graph theory, focusing on new methods which apply to different notions of regular graph: dregularity and Szemerédi regularity. We begin with a novel method for optimising observables of Gibbs distributions in sparse graphs. The simplest application of the method is to the hardcore model, concerning independent sets in dregular graphs, where we prove a tight upper bound on an observable known as the occupancy fraction. We also cover applications to matchings and colourings, in each case proving a tight bound on an observable of a Gibbs distribution and deriving an extremal result on the number of a relevant combinatorial structure in regular graphs. The results relate to a wide range of topics including statistical physics and Ramsey theory. We then turn to a form of Szemerédi regularity in sparse hypergraphs, and develop a method for embedding complexes that generalises a widelyapplied method for counting in pseudorandom graphs. We prove an inheritance lemma which shows that the neighbourhood of a sparse, regular subgraph of a highly pseudorandom hypergraph typically inherits regularity in a natural way. This shows that we may embed complexes into suitable regular hypergraphs vertexbyvertex, in much the same way as one can prove a counting lemma for regular graphs. Finally, we consider the multicolour Ramsey number of paths and even cycles. A wellknown density argument shows that when the edges of a complete graph on kn vertices are coloured with k colours, one can find a monochromatic path on n vertices. We give an improvement to this bound by exploiting the structure of the densest colour, and use the regularity method to extend the result to even cycles.

Counting the number of ways a gas can fill a roomMaths at LSE Blog (2016)
Graph theory is the study of connected systems of abstract ‘things’ which we call graphs. In this example the ‘things’ in the graph are particles of a gas or atoms in a molecule, and we describe a new method for understanding mathematical models in these graphs.
Past events

18 Oct 2017Discrete Mathematics Seminar, KdVI / CWI  Amsterdam, NetherlandsTitle: Shamir's problem revisited

28 Aug – 1 Sep 2017EUROCOMB 2017  Vienna, AustriaTitle: Tight bounds on the coefficients of partition functions via stability (31 Aug, slides)

17–21 Jul 2017Novi Sad Workshop on Foundations Of Computer Science  Novi Sad, SerbiaTitle: Regularity inheritance in 3uniform hypergraphs (20 Jul)

11 May 2017Two oneday Colloquia in Combinatorics (invited)  London, UKTitle: Tight bounds on the coefficients of partition functions via stability

21 Feb 2017Combinatorics Seminar  Oxford, UKTitle: Extremal problems on colourings in cubic graphs via the Potts model

3 Feb 2017Discrete Mathematics Seminar, KdVI / CWI  Amsterdam, NetherlandsTitle: A probabilistic approach to bounding graph polynomials

27 Jan 2017PhD Seminar on Combinatorics, Games and Optimisation, LSE  London, UKTitle: A probabilistic approach to bounding graph polynomials

3 Aug 2016Student Combinatorics Day (invited)  Birmingham, UKTitle: On the average size of independent sets in trianglefree graphs (slides)

8 Apr 2016Seminário de Teoria da Computação, Combinatória e Otimização  São Paulo, BrazilTitle: Independent sets, matchings, and occupancy fractions II

3 Nov 2015Discrete Geometry and Combinatorics Seminar, UCL  London, UKTitle: Independent sets, matchings, and occupancy fractions

9 Oct 2015Mathematics Lunchtime Seminar, LSE  London, UKTitle: Independent sets, matchings, and occupancy fractions I

31 Aug – 4 Sep 2015EUROCOMB 2015  Bergen, NorwayTitle: Counting in hypergraphs via regularity inheritance (31 Aug, slides)

15 Apr 2015Postgraduate Combinatorial Conference, QMUL  London, UKTitle: Counting in hypergraphs via regularity inheritance

9 Apr 2015Combinatorics Seminar, Freie Universität  Berlin, GermanyTitle: Regularity inheritance in 3uniform hypergraphs

3 Jul 2014SUMMIT 190: Balogh, Csaba, Hajnal, and Pluhar are 190 (invited)  Szeged, HungaryTitle: Robustness of triangle factors

29 Nov 2013Mathematics Lunchtime Seminar, LSE  London, UKTitle: Cycle packing