Combinatorics and Probability Seminar

The Combinatorics and Probability Seminar usually takes place on Thursdays at 15:00 during term time in Lecture Theatre C or A, Watson Building.

Spring 2020

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

  • Julian Sahasrabudhe (University of Cambridge)
  • Thursday 12 March 2020, 15:00
  • Watson LTC
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

Removing induced even cycles from a graph

  • Amarja Kathapurkar
  • Thursday 05 March 2020, 15:00
  • Watson LTA
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

A proof of Ringel's conjecture

  • Alexey Pokrovskiy (Birkbeck College, University of London)
  • Thursday 27 February 2020, 15:00
  • Watson LTC
  • Tea, coffee and biscuits will be provided after the talk at the common room

Ringel conjectured that the edges of the complete graph on2n+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.

Iterated product sets with shifts

  • Oliver Roche-Newton (RICAM, Austria)
  • Thursday 20 February 2020, 15:00
  • Watson LTA
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

Extremal problems of long cycles in random graphs

  • Gal Kronenberg (University of Oxford)
  • Thursday 13 February 2020, 15:00
  • Watson LTC
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

Counting Hamilton cycles in Dirac hypergraphs

  • Stephen Gould (University of Birmingham)
  • Thursday 06 February 2020, 15:00
  • Watson LTA
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

The Typical Structure of Sets with Small Sumset

  • Natasha Morrison (University of Cambridge)
  • Thursday 30 January 2020, 15:00
  • Watson LTC
  • Tea, coffee and biscuits will be provided after the talk at the common room

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 arithmeticprogression of length \lambda k/2 + \omega.

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

Homomorphisms from the torus

  • Matthew Jenssen (University of Birmingham)
  • Thursday 23 January 2020, 15:00
  • Watson LTA
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

Sampling sufficiency for determining modularity.

  • Fiona Skerman (University of Bristol)
  • Thursday 16 January 2020, 15:00
  • Watson LTC
  • Tea, coffee and biscuits will be provided after the talk at the common room

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.

Find out more

There is a complete list of talks in the seminar that can be accessed on talks@bham.