Past Combinatorial Theory Seminar

E.g., 2019-08-18
E.g., 2019-08-18
E.g., 2019-08-18
18 June 2019
14:30
Anita Liebenau

Further Information: 

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence? 

Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for 
the number of graphs with a given degree sequence, for a range of degree sequences that is wide enough to deduce asymptotic formulae for the second 
question for p =o(1/o(\sqrt(n))) and p = Theta(1).  

McKay and Wormald showed that the formulae for the sparse case and the 
dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent 
binomial variables Bin(n − 1, p'). 

In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings. 

  • Combinatorial Theory Seminar
4 June 2019
14:30
Annika Heckel

Further Information: 

A classic result of Shamir and Spencer states that for any function $p=p(n)$, the chromatic number of $G(n,p)$ is whp concentrated on a sequence of intervals of length about $\sqrt{n}$. For $p<n^{-\frac{1}{2} -\epsilon}$, much more is known: here, the chromatic number is concentrated on two consecutive values.

Until now, there have been no non-trivial cases where $\chi(G(n,p))$ is known not to be extremely narrowly concentrated. In 2004, Bollob\'as asked for any such examples, particularly in the case $p=\frac{1}{2}$, in a paper in the problem section of CPC. 

In this talk, we show that the chromatic number of $G(n, 1/2)$ is not whp concentrated on $n^{\frac{1}{4}-\epsilon}$ values

  • Combinatorial Theory Seminar
21 May 2019
14:30
Christoph Spiegel

Further Information: 

The Hales–Jewett Theorem states that any r–colouring of [m]^n contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.

  • Combinatorial Theory Seminar
14 May 2019
14:30
Michael Chapman

Further Information: 

Expander graphs play a key role in modern mathematics and computer science. Random d-regular graphs are good expanders. Recent developments in PCP theory require families of graphs that are expanders both globally and locally. The meaning of “globally" is the usual one of expansion in graphs, and locally means that for every vertex the subgraph induced by its neighbors is also an expander graph. These requirements are significantly harder to satisfy and no good random model for such (bounded degree) graphs is presently known. In this talk we discuss two new combinatorial constructions of such graphs. We also say something about the limitations of such constructions and provide an Alon-Bopanna type bound for the (global) spectral gap of such a graph. In addition we discuss other notions of high dimensional expansion that our constructions do and do not satisfy, such as coboundary expansion, geometric overlap and mixing of the edge-triangle-edge random walk. This is a joint work with Nati Linial and Yuval Peled.
 

  • Combinatorial Theory Seminar
7 May 2019
14:30
Marthe Bonamy

Further Information: 

In this talk, we will discuss various results around Brooks' theorem: a graph has chromatic number at most its maximum degree, unless it is a clique or an odd cycle. We will consider stronger variants and local versions, as well as the structure of the solution space of all corresponding colorings.

  • Combinatorial Theory Seminar
30 April 2019
14:30
Jozef Skokan

Further Information: 

Given positive integers n,r,k, the Erdős-Rothschild problem asks to determine the largest number of r-edge-colourings without monochromatic k-cliques a graph on n vertices can have. In the case of triangles, i.e. when k=3, the solution is known for r = 2,3,4. We investigate the problem for five and six colours.

  • Combinatorial Theory Seminar
26 February 2019
14:30
Maryam Sharifzadeh

Further Information: 

Among all graphs of given order and size, we determine the asymptotic structure of graphs which minimise the number of $r$-cliques, for each fixed $r$. In fact, this is achieved by characterising all graphons with given density which minimise the $K_r$-density. The case $r=3$ was proved in 2016 by Pikhurko and Razborov.

 

This is joint work with H. Liu, J. Kim, and O. Pikhurko.

  • Combinatorial Theory Seminar
19 February 2019
14:30
Katherine Staden

Further Information: 

Recently, much progress has been made on the general problem of decomposing a dense (usually complete) graph into a given family of sparse graphs (e.g. Hamilton cycles or trees). I will present a new result of this type: that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A special case of this result reproves the Oberwolfach problem for large graphs.

 

This is joint work with Peter Keevash.

  • Combinatorial Theory Seminar
12 February 2019
14:30
Svante Janson
Abstract

We study random (simple) graphs with given vertex degrees, in the sparse case where the average degree is bounded. Assume also that the second moment of the vertex degree is bounded. The standard method then is to use the configuration model to construct a random multigraph and condition it on
being simple.

This works well for results of the type that something holds with high probability, or that something converges in probability, but it does not immediately apply to convergence in distribution, for example asymptotic normality. (Although this has been done by special arguments in a couple of cases, by Janson and Luczak and by Riordan.) A typical example is the recent result by Barbour and Röllin on asymptotic normality of the size of the giant component of the multigraph (in the supercritical case); it is an obvious conjecture that the same results hold for the random simple graph.

We discuss two new approaches to this, both based on old methods. Both apply to the size of the giant component, using rather minor special arguments.

One approach uses the method of moments to obtain joint convergence of the variable of interest together with the numbers of loops and multiple edges
in the  multigraph.

The other approach uses switchings to modify the multigraph and construct a simple graph. This simple random graph will not have a uniform distribution,
but almost, and this is good enough.

  • Combinatorial Theory Seminar
29 January 2019
14:30
Guillem Perarnau
Abstract

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree \Delta is rapidly mixing for k \ge \Delta+2. In 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper k-colorings for k > (11/6)\Delta, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the (11/6)\Delta barrier for general graphs by showing rapid mixing for k > (11/6 - \eta)\Delta for some positive constant \eta. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda’s 2007 survey paper on Glauber dynamics for colorings. 


This is joint work with Michelle Delcourt and Luke Postle.

 
  • Combinatorial Theory Seminar

Pages