Past Events

 

 

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 Ω(N1/2) distinct degrees. We improve this to Ω(N2/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=Ω(k9) 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.

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.

Homomorphisms from the torus

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus Zn_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 Zn_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.

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.

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.

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.

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.

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.

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.

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.

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