Combinatorics Seminar

For 2024-25, the Combinatorics Seminar will be held 2-3pm on Fridays in B3.02, unless otherwise stated.

In Term 3, the seminar is organised by Natalie Behague, Debsoumya Chakraborti and Richard Montgomery. Abstracts will be added below the table when details are available.

Term 3

25th April: Asaf Cohen Antonir, Tel Aviv University

Weak saturation and collapsible complexes in a random graph

30th May: Daniel Kral (Leipzig University and MPI MiS)

Curves on the torus with prescribed intersections

Juvan, Malnič and Mohar [J. Combin. Theory Ser. B 68 (1996), 7-22] proved that for every surface S and every integer k, there exists N(S,k) such that any set of simple closed curves on the surface S, where any two are non-homotopic and intersect at most k times, has a maximum size at most N(S,k). In the case when S is the torus T^2, the problem has an interesting connection to number theory as the Riemann hypothesis yields that N(T^2,k)<=k+O(k^0.5*log k); Aougab and Gaster [Math. Proc. Cambridge Philos. Soc. 174 (2023), 569-584] proved N(T^2,k)<=k+O(k^0.5*log k) directly. We compute N(T^2,k) for every k and in particular show that N(T^2,k)<=k+6 for all k and N(T^2,k)<=k+4 when k is sufficiently large.

The talk is based on joint work with Igor Balla, Marek Filakovský, Bartłomiej Kielak and Niklas Schlomberg.

6th June: Adva Mond (King's College London)

Approximate Itai-Zehavi conjecture for random graphs

13th June: Rob Silversmith (Warwick)

In Term 2, the seminar is organised by Natalie Behague, Debsoumya Chakraborti, Agelos Georgakopoulos and Richard Montgomery. Abstracts will be added below the table when details are available.

Term 2

10th Jan: Xizhi Liu, Warwick

An invitation to the density Hajnal--Szemer\'{e}di problem

31st Jan: Agelos Georgakopoulos, Warwick

A survey of coarse graph theory

I will survey results and open questions on 'coarse graph theory', an emerging area that combines ideas from graph theory and coarse geometry.

7th Feb: Sayan Mukherjee, University of Tokyo

Spectral graph clustering and local differential privacy

Finding clusters in graphs is an important problem in social network analysis. Of the many ways of finding such clusters, spectral clustering is widely used for the ease of implementation and its approximation guarantees via the Cheeger inequalities. However, simply publishing information about clusters in a social network leads to leakage in privacy. In a locally differentially private graph algorithm, users locally perturb their adjacency data before sending it to a central server, which then makes some inference on the perturbed graph. With proper addition of noise, it can be possible to protect users' privacy while still making statistical inference about the underlying social networks. In this talk, we will analyze the robustness of the spectral clustering algorithm under the addition of noise in the adjacency information.

14th Feb: Marc Distel, Monash University

Further improvements to the product structure extension of the Alon-Seymour-Thomas theorem

Alon, Seymour, and Thomas [1990] showed that every $n$ vertex graph that excludes $K_t$ as a minor has treewidth and pathwidth at most $O_t(\sqrt{n})$. Distel, Dujmović, Eppstein, Hickingbotham, Joret, Micek, Morin, Seweryn, and Wood [2024] expanded on this, showing that these graphs could be written as a $O_t(\sqrt{n})$-blowup of a treewidth 4 graph. I further refine this, by showing that the treewidth 4 can be replaced by treewidth 3, and can be further reduced to pathwidth 2 if you allow the blowup to have size $O_t(\sqrt{n}\log(n)^2)$.

19th Feb: Karim Adiprasito, Jussieu Institute of Mathematics - Paris Rive Gauche

(Open) Extremal problems in combinatorics and algebra

Algebraic combinatorics and extremal combinatorics are, sadly, almost disjoint. Algebraic combinatorics deals with isomorphisms, and is an exact science. Extremal combinatorics is a study of a more quantitative nature. Hence, marrying the two is difficult. I will outline several problems that attempt to quantify "algebraic" results and present some results and open problems. This talk is more of a challenge with many open problems rather than results :)

21st Feb: Sandra Albrechtsen, Hamburg University

Asymptotic and diverging half- and full-grid minors

Georgakopoulos and Hamann [2024] showed that every locally finite, quasi-transitive graph $G$ that is not quasi-isometric to a tree contains the full-grid as a minor.

In this talk I discuss how this result could be strengthened so that the full-grid minor appears in the coarse (`large-scale') geometry of $G$. For this, I define asymptotic minors and diverging minors and describe how the full-grid can be found as such minors in $G$ if $G$ has the additional property that its cycle space is generated by cycles of bounded length. In particular, it follows that all locally finite Cayley graphs of finitely presented groups that are not virtually free contain the full-grid as an asymptotic minor and as a diverging minor.

Additionally, I discuss assumptions which ensure that a (not necessarily quasi-transitive) graph contains the half-grid as an asymptotic minor and as a diverging minor.

This is based on joint work with Matthias Hamann.

28th Feb: Nora Frankl, Open University

The Quantitative Helly Theorem

Helly's theorem states that if the intersection of any d+1 members of a finite family F of convex sets in R^d is nonempty, then the intersection of the whole family is nonempty. The Fractional Helly theorem of Katchalski and Liu, and the Quantitative Helly theorem of Bárány, Katchalski, and Pach are two famous extensions of this result. Improving on several recent works, we prove an optimal combination of these two extensions. We show that if a positive fraction of the (d+1)-tuples of F intersect in large volume, then a positive fraction of F intersects in large volume as well. Joint work with Attila Jung and Istvan Tomon.

7th March: Andrew Treglown, University of Birmingham

Arbitrary orientations of Hamilton cycles in directed graphs

In 1960, Ghouila-Houri proved that every strongly connected directed graph G on n vertices and with minimum degree at least n contains a directed Hamilton cycle. We asymptotically generalize this result by proving the following: every directed graph G on n vertices and with minimum degree more than (1+o(1))n contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle in the case when G is not strongly connected.

This is joint work with Louis DeBiasio.

11th March: Maksim Zhukovskii, University of Sheffield

The sharp threshold for the square of a Hamilton cycle

In 2020, Kahn, Narayanan, and Park conjectured that the probability threshold for the binomial random graph G(n,p) to contain the square of a Hamilton cycle is (1+o(1))\sqrt{e/n}. In the talk, I will present a proof of this conjecture. Although the proof relies on the fragmentation technique, as the original proof by Kahn, Narayanan and Park for establishing a coarse threshold, the way of selecting fragments is essentially different. One of the main ingredients of the proof is the fact that sufficiently many squares of cycles have fragments that avoid squares of paths of length at least logarithmic in n with high probability.

14th March: Shoham Letzter, University College London

Almost covering regular graphs by F-subdivisions

In Term 1, the seminar was organised by Natalie Behague, Debsoumya Chakraborti and Richard Montgomery.

Term 1

4th Oct: Akshat Mudgal, University of Warwick

Approximating sumset estimates via translates

A finite, non-empty subset A of Z^d is defined to be d-dimensional if it is not contained in a translate of some hyperplane. Given a d-dimensional set A of cardinality N, a classical result in additive combinatorics known as Freiman’s lemma implies that

|A+A| >= (d+1)N - d(d+1)/2.

Moreover, this estimate is sharp.

In the spirit of some recent work of Bollobas–Leader–Tiba, it is natural to ask whether one can approximate this lower bound by just considering a few translates of A. In joint work with Yifan Jing we prove precisely this, that is, for any d-dimensional set A with N elements, there exists a subset X of A with |X| = O_d(1) such that

|A+X| >= (d+1)N - d(d+1)/2.

11th Oct: Ella Williams, UCL

Covering vertices with monochromatic paths

Abstract: In 1995, Erd\H{o}s and Gy\'arf\'as proved that in every 2-edge-coloured complete graph on $n$ vertices, there exists a collection of $2\sqrt{n}$ monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured that it is possible to replace $2\sqrt{n}$ by $\sqrt{n}$. We prove this to be true for all sufficiently large $n$.

This is based on joint work with Alexey Pokrovskiy and Leo Versteegen.

18th Oct: Camila Zárate-Guerén, University of Birmingham

Colour-bias perfect matchings in hypergraphs

Given a k-uniform hypergraph H on n vertices with an r-colouring of its edges, we look for a minimum l-degree condition that guarantees the existence of a perfect matching in H that has more than n/rk edges in one colour. We call this a colour-bias perfect matching.

For 2-coloured graphs, a result of Balogh, Csaba, Jing and Pluhár yields the minimum degree threshold that ensures a perfect matching of significant colour-bias. In this talk, I will present an analogous of this result for k-uniform hypergraphs. More precisely, for each 1<=l<k and r>=2 we determined the minimum l-degree threshold that forces a perfect matching of significant colour-bias in an r-edge-coloured k-uniform hypergraph.

The presented result is joint work with J. Balogh, H. Hàn, R. Lang, J. P. Marciano, M. Pavez-Signé, N. Sanhueza-Matamala and A. Treglown.

25th Oct: Sarah Selkirk, University of Warwick

Directed lattice paths with negative boundary

1st Nov: Marius Tiba, King's College London

Upper bounds for multicolour Ramsey numbers