Institution: London School of Economics and Political Science
Status: PhD Student
Advisors: Peter Allen and Jozef Skokan
Email: B.J.Roberts@lse.ac.uk
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on n vertices with maximum degree d, showing that an independent set drawn uniformly at random from such a graph has expected size at least (1 + o(1))n *log d / d. This gives an alternative proof of Shearer’s upper bound on the Ramsey number R(3, k). We then prove that the total number of independent sets in a triangle-free graph with maximum degree d is at least exp[(1/2 + o(1))n*log^2 d / d]. The constant 1/2 in the exponent is best possible. In both cases, tightness is exhibited by a random d-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set I drawn from a graph with probability proportional to λ^|I| , for a fugacity parameter λ > 0. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree d. The bound is asymptotically tight in d for all λ = O(1) as d tends to infinity. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that (k − 1)n + o(n) ≤ Rk(Pn) ≤ Rk(Cn) ≤ kn + o(n). The upper bound was recently improved by Sárközy. Here we show Rk(Cn) ≤ (k − 1/4)n + o(n), obtaining the first improvement to the coefficient of the linear term by an absolute constant. The general idea is to consider some counter-example G on N=(k- 1/4)n vertices and try to arrive at a contradiction. We start by showing that the densest colour (blue say) has roughly k connected components none of which is too large. From this we can get a bound on the number of edges (blue or otherwise) lying within blue components. We then bound above the number of edges in remaining colours going between different blue components. We then give bounds on how many edges a multipartite graph can have without containing a path (or even cycle) and use this to bound the number of edges in each colour going between blue components. Putting these two bounds together gives a bound on the total number of edges of G. This bound is less than N(N-1)/2 which is a contradiction.
We determine the Ramsey number of a connected clique matching. That is, we show that if G is a 2-edge-coloured complete graph on (r^2 − r − 1)n − r + 1 vertices, then there is a monochromatic connected subgraph containing n disjoint copies of Kr, and that this number of vertices cannot be reduced. This extends work of Gyárfás and Sárközy who proved the triangle case, r=3. The lower bound comes from a construction of Burr that gives a general lower bound for the Ramsey number of a connected graph with chromatic number r. Of course we cannot expect to solve this problem for small n as we then push towards looking at bounds on R(Kr). In fact we require that n > R(Kr). The proof is elementary and short.
We give tight upper bounds on the logarithmic derivative of the independence and matching polynomials of any d-regular graph.
For independent sets, this is a strengthening of a sequence of results of Kahn, Galvin and Tetali, and Zhao that a disjoint union of K_dd's maximizes the independence polynomial and total number of independent sets among all d-regular graphs.
For matchings, the result implies that disjoint unions of K_dd's maximize the matching polynomial and total number of matchings, as well as proving the asymptotic upper matching conjecture of Friedland, Krop, Lundow, and Markstrom.
The proof uses an occupancy method: we show that the occupancy fraction in the hard-core model and the edge occupancy fraction in the monomer-dimer model are maximized over all d-regular graphs by K_dd.
From Andrásfai-Erdős-Sós in 1974 to 2006 with Brandt-Thomassé a series of results showed that minimum degree conditions on triangle-free graphs lead to structure in the form of small chromatic number. We give random graph analogues of two such theorems - that of Andrásfai-Erdős-Sós and also a theorem of Thomassen. Roughly speaking our results show that triangle-free spanning subraphs of G(n,p) with minimum degree conditions corresponding to those of the classical results are close to having the corresponding bound on chromatic number. Here close means only a few edges need to be removed to obtain this statement. More specifically if triangle-free H - a subgraph of G(n,p) - has minimum degree at least (2/5 + o(1))pn then only O(n/p) edge removals are needed to make H bipartite. If H has minimum degree at least (1/3 + o(1))pn then after O(n/p) edge removals the graph can be made O(1)-colourable. We show our results to be best possible up to a constant factor.
A graph G is 'H-saturated' if it contains no copy of H but would do with the addition of any extra edge. Saturation problems typically ask for the least possible edges in an H-saturated graph on some fixed number of vertices. Such problems complement Turan type questions which can be viewed as looking for the H-saturated graphs with most edges. The definition can be extended so that for a small graph H and large graph F we say G is (H,F)-saturated is G is an H-free subgraph of F such that adding any extra edge of F to G would result in a copy of H. The usual notion is then (H,K_n)-saturation. In this paper we consider the case where F is a blow-up of H and where we restrict our attention to copies of H which respect the implied partition on G (from F). In particular we determine the exact (K_4,K_4[n])-saturation number where K_4[n] is a blow-up of K_4 onto parts of size n. We solve the same problem for paths and stars and show a dicotomy of behaviour depending on whether the graph H is 2-connected or not.