**Past Combinatorics Seminars**

** 2019/20
**

## Sharp thresholds for sparse functions with applications to extremal combinatorics

The sharp threshold phenomenon is a central topic of research in the analysis of Boolean functions. Here, one aims to give sufficient conditions for a monotone Boolean function f to satisfy ÎŒ_p(f)=o(ÎŒ_q(f)), where q = p + o(p), and ÎŒ_p(f) is the probability that f=1 on an input with independent coordinates, each taking the value 1 with probability p.

The dense regime, where ÎŒ_p(f)=Î(1), is somewhat understood due to seminal works by Bourgain, Friedgut, Hatami, and Kalai. On the other hand, the sparse regime where ÎŒ_p(f)=o(1) was out of reach of the available methods. However, the potential power of the sparse regime was envisioned by Kahn and Kalai already in 2006.

In this talk we show that if a monotone Boolean function f with ÎŒ_p(f)=o(1) satisfies some mild pseudo-randomness conditions then it exhibits a sharp threshold in the interval [p,q], with q = p+o(p). More specifically, our mild pseudo-randomness hypothesis is that the p-biased measure of f does not bump up to Î(1) whenever we restrict f to a sub-cube of constant co-dimension, and our conclusion is that we can find q=p+o(p), such that ÎŒ_p(f)=o(ÎŒ_q(f))

At its core, this theorem stems from a novel hypercontactive theorem for Boolean functions satisfying pseudorandom conditions, which we call `small generalized influencesâ. This result takes on the role of the usual hypercontractivity theorem, but is significantly more effective in the regime where p = o(1).

We demonstrate the power of our sharp threshold result by reproving the recent breakthrough result of Frankl on the celebrated Erdos matching conjecture, and by proving conjectures of HuangâLohâSudakov and FurediâJiang for a new wide range of the parameters.

Based on a joint work with Peter Keevash, Eoin Long, and Dor Minzer.

- Part of Combinatorics and Probability seminar
- Speaker: Noam Lifshitz (Hebrew University)
- Thursday 03 October 2019, 14:00-15:00
- Watson LTB.

## 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.

- Part of Combinatorics and Probability seminar
- Speaker: Oliver Janzer (University of Cambridge)
- Thursday 10 October 2019, 14:00-15:00
- Watson LTB.

## Path and cycle decompositions of dense graphs

We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on n vertices can be decomposed into at most ân/2â paths, while a conjecture of HajĂłs states that any Eulerian graph on n vertices can be decomposed into at most â(n-1)/2â cycles. The ErdĆs-Gallai conjecture states that any graph on n vertices can be decomposed into O(n) cycles and edges.

We show that if G is a sufficiently large graph on n vertices with linear minimum degree, then the following hold. (i) G can be decomposed into n/2+o(n) paths. (ii) If G is Eulerian, then it can be decomposed into n/2+o(n) cycles. (iii) G can be decomposed into 3n/2+o(n) cycles and edges. All bounds in (i)-(iii) are asymptotically best possible.

This is joint work with AntĂłnio GirĂŁo, Daniela KĂŒhn, and Deryk Osthus.

- Part of Combinatorics and Probability seminar
- Speaker: Bertille Granet (University of Birmingham)
- Thursday 17 October 2019, 14:00-15:00
- Watson LTB.

## Partial associativity in Latin squares

Latin squares arise from the multiplication tables of groups, but the converse is not true in general. Given a Latin square A, we can define a group operation giving A as its multiplication table only when A satisfies a suitable associativity constraint. This observation leads to a natural question, originating with Hrushovski, concerning the â1%â version: if A is only partially associative, can we still obtain something resembling a group structure? I will talk about some joint work with Tim Gowers on this question.

- Part of Combinatorics and Probability seminar
- Speaker: Jason Long (University of Oxford)
- Thursday 24 October 2019, 14:00-15:00
- Watson LTB.

## On the density of critical graphs without large cliques

A graph is k-critical if it has chromatic number k and every proper subgraph is (k-1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to a possible generalization of Reedâs Conjecture.

Joint work with Luke Postle.

- Part of Combinatorics and Probability seminar
- Speaker: Tom Kelly (University of Birmingham)
- Thursday 31 October 2019, 14:00-15:00
- Watson LTB.

## 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 polylogarithmic factor (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.

- Part of Combinatorics and Probability seminar
- Speaker: NĂłra Frankl (LSE)
- Thursday 07 November 2019, 14:00-15:00
- Watson LTB.

## A degree sequence KomlĂłs theorem

Given graphs G and H, we define an H-tiling in G to be a collection of vertex-disjoint copies of H in G. Let Î· > 0. We call an H-tiling perfect if it covers all of the vertices in G and Î·-almost perfect if it covers all but at most an Î·-proportion of the vertices in G. An important theorem of KomlĂłs provides the minimum degree of G which ensures an Î·-almost perfect H-tiling in G. We present a degree sequence strengthening of this result and provide a proof sketch. This is joint work with Hong Liu and Andrew Treglown.

Using the aforementioned theorem of KomlĂłs, KĂŒhn and Osthus determined the minimum degree of G that ensures a perfect H-tiling in G. We present a degree sequence version of their result as an application of our degree sequence KomlĂłs theorem. This is joint work with Andrew Treglown.

- Part of Combinatorics and Probability seminar
- Speaker: Joseph Hyde (University of Birmingham)
- Thursday 14 November 2019, 14:00-15:00
- Watson LTB.

## Nonlinear problems in arithmetic Ramsey theory

Rado characterised those systems of linear Diophantine equations which are âunbreakableâ with respect to finite partitions, so that any partition of the positive integers yields a set containing a solution. Similarly, a celebrated theorem of SzemerĂ©di gives rise to a characterisation of linear systems possessing solutions in any âdenseâ set of integers. We discuss variants of these results for certain nonlinear equations/configurations.

- Part of Combinatorics and Probability seminar
- Speaker: Sean Prendiville (Lancaster University)
- Thursday 21 November 2019, 14:00-15:00
- Watson LTB.

## The ErdĆs Sumset Conjecture

ErdĆs asked whether every set of natural numbers with positive density contains the (arithmetic) sum B+C of two infinite sets B and C of natural numbers. In joint work with Florian Richter and Donald Robertson we answered this question affirmatively, borrowing some ideas from ergodic theory. I will talk about this and related questions, several of which are still open, and then explain the main ideas that go into the proof.

- Part of Combinatorics and Probability seminar
- Speaker: Joel Moreira (University of Warwick)
- Thursday 05 December 2019, 14:00-15:00
- Watson LTB.

## Distinct degrees in induced subgraphs

An important theme of recent research in Ramsey theory has been
establishing pseudorandomness properties of Ramsey graphs. An N-vertex
graph is called *C-Ramsey* if it has no homogeneous set of size
Clog(N). A theorem of Bukh and Sudakov, solving a conjecture of ErdĆs,
Faudree and SĂłs, shows that any C-Ramsey N-vertex graph contains an
induced subgraph with Î©(N^{1/2}) distinct degrees. We improve this to Î©(N^{2/3}), which is tight up to the constant factor.

We also show that any N-vertex graph with N > (kâ1)(nâ1) and n=Î©(k^{9})
either contains a homogeneous set of order n or an induced subgraph
with k distinct degrees. The lower bound on N here is sharp, as shown by
an appropriate TurĂĄn graph, and confirms a conjecture of Narayanan and
Tomon.

Joint work with Matthew Jenssen, Peter Keevash and Liana Yepremyan.

- Part of Combinatorics and Probability seminar
- Speaker: Eoin Long (University of Birmingham)
- Thursday 12 December 2019, 14:00-15:00
- Watson LTB.

## Sampling sufficiency for determining modularity.

Modularity is used in popular algorithms for community detection. For
a given network G, each partition of the vertices has a modularity
score, with higher values indicating that the partition better
captures community structure in G. The (max) modularity q** of the network G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 â€ q**(G) â€ 1.

We analyse when community structure of an underlying network can be determined from its observed network. In a natural model where we suppose edges in an underlying graph G appear with some probability in our observed graph Gâ we describe how high a sampling probability we need to infer the community structure of the underlying network.

Joint work with Colin McDiarmid.

- Part of Combinatorics and Probability seminar
- Speaker: Fiona Skerman (University of Bristol)
- Thursday 16 January 2020, 15:00-16:00
- Watson LTC.

## Homomorphisms from the torus

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus Z^{n}_m,
where m is even, to any fixed graph. We show that the corresponding
probability distribution on such homomorphisms is close to a
distribution defined constructively as a certain random perturbation of
some âdominant phaseâ. This has several consequences, including
solutions (in a strong form) to conjectures of Engbers and Galvin and a
conjecture of Kahn and Park. Special cases include sharp asymptotics for
the number of independent sets and the number of proper q-colourings of
Z^{n}_m (so in particular, the discrete hypercube). For the
proof we develop a `Cluster Expansion Methodâ, which we expect to have
further applications, by combining machinery from statistical physics,
entropy and graph containers. This is joint work with Peter Keevash.

- Part of Combinatorics and Probability seminar
- Speaker: Matthew Jenssen (University of Birmingham)
- Thursday 23 January 2020, 15:00-16:00
- Watson LTA.

## The Typical Structure of Sets with Small Sumset

One of the central objects of interest in additive combinatorics is the sumset A+B= {a+b:a \in A, b \in B} of two sets A,B of integers.

Our main theorem, which improves results of Green and Morris, and of Mazur, implies that the following holds for every fixed \lambda > 2 and every k>(log n)^4: if \omega goes to infinity as n goes to infinity (arbitrarily slowly), then almost all sets A of [n] with |A| = k and |A + A| < \lambda k are contained in an arithmetic progression of length \lambda k/2 + \omega.

This is joint work with Marcelo Campos, Mauricio Collares, Rob Morris and Victor Souza.

- Part of Combinatorics and Probability seminar
- Speaker: Natasha Morrison (University of Cambridge)
- Thursday 30 January 2020, 15:00-16:00
- Watson LTC.

## Counting Hamilton cycles in Dirac hypergraphs

A tight Hamilton cycle in a k-uniform hypergraph (k-graph) G is a cyclic ordering of the vertices of G such that every set of k consecutive vertices in the ordering forms an edge. RĂ¶dl, RuciĆski, and SzemerĂ©di proved that for kâ„3, every k-graph on n vertices with minimum codegree at least n/2+o(n) contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such k-graphs is exp(n ln n â Î(n)). As a corollary, we obtain a similar estimate on the number of Hamilton l-cycles in such k-graphs for all lâ{0,âŠ,kâ1}, which addresses a question of Ferber, Krivelevich and Sudakov.

This is joint work with Stefan Glock, Felix Joos, Daniela KĂŒhn, and Deryk Osthus.

- Part of Combinatorics and Probability seminar
- Speaker: Stephen Gould (University of Birmingham)
- Thursday 06 February 2020, 15:00-16:00
- Watson LTA.

## Extremal problems of long cycles in random graphs

In this talk, we consider the random version of some classical extremal problems in the context of long cycles. This type of problems can also be seen as random analogues of the TurĂĄn number of long cycles, established by Woodall in 1972.

For a graph G on n vertices and a graph H, denote by ex(G,H) the maximal number of edges in an H-free subgraph of G. We consider a random graph G~G(n,p) where p>C/n, and determine the asymptotic value of ex(G,C_t), for every A*log(n)< t< (1- Æ)n. The behaviour of ex(G,C_t) can depend substantially on the parity of t. In particular, our results match the classical result of Woodall, and demonstrate the transference principle in the context of long cycles.

Using similar techniques, we also prove a robustness-type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density (a nearly ââWoodall graphâ). If time permits, we will present some connections to size-Ramsey numbers of long cycles.

Based on joint works with Michael Krivelevich and Adva Mond.

- Part of Combinatorics and Probability seminar
- Speaker: Gal Kronenberg (University of Oxford)
- Thursday 13 February 2020, 15:00-16:00
- Watson LTC.

## Iterated product sets with shifts

An important variant of the sum-product problem is the following: given a finite set A, show that either its product set is large, or any translate of A has large product set. I will discuss a joint work with Hanson and Zhelezov, in which we prove bounds for this problem with many variables in the rational setting. The proof is based on a deep work of Bourgain and Chang on the sum-product problem, although the analysis has thankfully now been greatly simplified owing to a new result of Palvolgyi and Zhelezov which gives powerful structural information about sets of rationals with small product sets.

- Part of Combinatorics and Probability seminar
- Speaker: Oliver Roche-Newton (RICAM, Austria)
- Thursday 20 February 2020, 15:00-16:00
- Watson LTA.

## A proof of Ringel's conjecture

Ringel conjectured that the edges of the complete graph on 2n+1 vertices can be decomposed into disjoint copies of any n-edge tree T. This talk will be about a recent proof of this conjecture for sufficiently large n.

This is joint work with Richard Montgomery and Benny Sudakov.

- Part of Combinatorics and Probability seminar
- Speaker: Alexey Pokrovskiy (Birkbeck College, University of London)
- Thursday 27 February 2020, 15:00-16:00
- Watson LTC.

## Removing induced even cycles from a graph

What is the minimum proportion of edges which must be added to or removed from a graph of density p to eliminate all induced cycles of length h? The maximum of this quantity over all graphs of density p is measured by the edit distance function, ed_{Forb(C_h)}(p). Edit distances provide a natural metric between graphs and hereditary properties.

Martin and Peck determined ed_{Forb(C_h)}(p) for all p for odd cycles, and for p\geq 1/\lceil h/3 \rceil for even cycles. We improve on this result for even cycles by determining the function for all p \geq p_0, where p_0 \leq c/h^2, for some constant c. We also prove an analogous result for powers of cycles which holds for every p in [0,1], thus improving on a result of Berikkyzy, Martin, and Peck.

This is joint work with Richard Mycroft.

- Part of Combinatorics and Probability seminar
- Speaker: Amarja Kathapurkar
- Thursday 05 March 2020, 15:00-16:00
- Watson LTA.

## Combinatorial discrepancy and a problem of J.E. Littlewood on Flat Polynomials

Given a collection of sets A1,...,Am â [n], the basic problem in combinatorial discrepancy theory is to find a colouring of {1,...,n} with {+1,-1} so that, for each i â [m], the sum of f over the elements A_i is as small in absolute value as possible. In this talk, I will discuss how the sort of combinatorial and probabilistic reasoning used to think about problems in combinatorial discrepancy can be adapted to solve an old conjecture of J.E. Littlewood in harmonic analysis.

- Part of Combinatorics and Probability seminar
- Speaker: Julian Sahasrabudhe (University of Cambridge+
- Thursday 12 March 2020, 15:00-16:00
- Watson LTC.

Previous seminars: Autumn 2006, Spring 2007, Autumn 2007, Spring 2008, Autumn 2008, Spring 2009, Autumn 2009, Spring 2010, 2010-2016, 2016/17, 2017/18, 2018/19, 2019/20, 2020/21, 2021/22, 2022/23