L6

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. 

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

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.

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.

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.