We purify and generalize some techniques which were successful in the limit theory of graphs and other discrete structures. We demonstrate how this technique can be used for solving different combinatorial problems, by defining the limit problems of the Manickam--Miklós--Singhi Conjecture, the Kikuta–Ruckle Conjecture and Alpern's Caching Game.

# Past Combinatorial Theory Seminar

Many of the fastest known algorithms for factoring large integers rely on finding subsequences of randomly generated sequences of integers whose product is a perfect square. Motivated by this, in 1994 Pomerance posed the problem of determining the threshold of the event that a random sequence of N integers, each chosen uniformly from the set

{1,...,x}, contains a subsequence, the product of whose elements is a perfect square. In 1996, Pomerance gave good bounds on this threshold and also conjectured that it is sharp.

In a paper published in Annals of Mathematics in 2012, Croot, Granville, Pemantle and Tetali significantly improved these bounds, and stated a conjecture as to the location of this sharp threshold. In recent work, we have confirmed this conjecture. In my talk, I shall give a brief overview of some of the ideas used in the proof, which relies on techniques from number theory, combinatorics and stochastic processes. Joint work with Béla Bollobás and Robert Morris.

For a fixed degree sequence D=(d_1,...,d_n), let G(D) be a uniformly chosen (simple) graph on {1,...,n} where the vertex i has degree d_i. The study of G(D) is of special interest in order to model real-world networks that can be described by their degree sequence, such as scale-free networks. While many aspects of G(D) have been extensively studied, most of the obtained results only hold provided that the degree sequence D satisfies some technical conditions. In this talk we will introduce a new approach (based on the switching method) that allows us to study the random graph G(D) imposing no conditions on D. Most notably, this approach provides a new criterion on the existence of a giant component in G(D). Moreover, this method is also useful to determine whether there exists a percolation threshold in G(D). The first part of this talk is joint work with F. Joos, D. Rautenbach and B. Reed, and the second part, with N. Fountoulakis and F. Joos.

For any given graph H, we may define a natural corresponding functional ||.||_H. We then say that H is norming if ||.||_H is a semi-norm. A similar notion ||.||_{r(H)} is defined by || f ||_{r(H)}:=|| | f | ||_H and H is said to be weakly norming if ||.||_{r(H)} is a norm. Classical results show that weakly norming graphs are necessarily bipartite. In the other direction, Hatami showed that even cycles, complete bipartite graphs, and hypercubes are all weakly norming. Using results from the theory of finite reflection groups, we demonstrate that any graph which is edge-transitive under the action of a certain natural family of automorphisms is weakly norming. This result includes all previous examples of weakly norming graphs and adds many more. We also include several applications of our results. In particular, we define and compare a number of generalisations of Gowers' octahedral norms and we prove some new instances of Sidorenko's conjecture. Joint work with David Conlon.

In the theory of random graphs, the behaviour of the typical largest component was studied a lot. The initial results on G(n,m), the random graph on n vertices and m edges, are due to Erdős and Rényi. Recently, similar results for planar graphs were obtained by Kang and Łuczak.

In the first part of the talk, we will extend these results on the size of the largest component further to graphs embeddable on the orientable surface S_g of genus g>0 and see how the asymptotic number and properties of cubic graphs embeddable on S_g are used to obtain those results. Then we will go through the main steps necessary to obtain the asymptotic number of cubic graphs and point out the main differences to the corresponding results for planar graphs. In the end we will give a short outlook to graphs embeddable on surfaces with non-constant genus, especially which results generalise and which problems are still open.

Given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs? This question is a natural graph-theoretic generalisation of the 'multiplication table problem' of Erdős: Erdős’s problem of estimating the number of distinct products a.b with a, b in [n] is precisely the problem under consideration when the graph in question is the complete bipartite graph K_{n,n}.

Based on joint work with J. Sahasrabudhe and I. Tomon.

Ramsey classes may be viewed as the top of the line of Ramsey properties. Classical and not so classical examples of Ramsey classes of finite structures were recently extended by many new examples which make the characterisation of Ramsey classes realistic (and in many cases known). Particularly I will cover recent joint work with J. Hubicka.

The size Ramsey number r'(H) of a graph H is the smallest number of edges in a graph G which is Ramsey with respect to H, that is, such that any 2-colouring of the edges of G contains a monochromatic copy of H. A famous result of Beck states that the size Ramsey number of the path with n vertices is at most bn for some fixed constant b > 0. An extension of this result to graphs of maximum degree ∆ was recently given by Kohayakawa, Rödl, Schacht and Szemerédi, who showed that there is a constant b > 0 depending only on ∆ such that if H is a graph with n vertices and maximum degree ∆ then r'(H) < bn^{2 - 1/∆} (log n)^{1/∆}. On the other hand, the only known lower-bound on the size Ramsey numbers of bounded-degree graphs is of order n (log n)^c for some constant c > 0, due to Rödl and Szemerédi.

Together with David Conlon, we make a small step towards improving the upper bound. In particular, we show that if H is a ∆-bounded-degree triangle-free graph then r'(H) < s(∆) n^{2 - 1/(∆ - 1/2)} polylog n. In this talk we discuss why 1/∆ is the natural "barrier" in the exponent and how we go around it, why we need the triangle-free condition and what are the limits of our approach.

There is an obvious product-free subset of the symmetric group of density 1/2, but what about the alternating group? An argument of Gowers shows that a product-free subset of the alternating group can have density at most n^(-1/3), but we only know examples of density n^(-1/2 + o(1)). We'll talk about why in fact n^(-1/2 + o(1)) is the right answer, why

Gowers's argument can't prove that, and how this all fits in with a more general 'product mixing' phenomenon. Our tools include some nonabelian Fourier analysis, a version of entropy subadditivity adapted to the symmetric group, and a concentration-of-measure result for rearrangements of inner products.