Source author record

Barnaby Roberts

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A robust Corrádi--Hajnal Theorem

For a graph $G$ and $p\in[0,1]$ , we denote by $G_p$ the random sparsification of $G$ obtained by keeping each edge of $G$ independently, with probability $p$ . We show that there exists a $C>0$ such that if $p\geq C(\log n)^{1/3}n^{-2/3}$ and $G$ is an $n$ -vertex graph with $n\in 3\mathbb{N}$ and $δ(G)\geq \tfrac{2n}{3}$ , then with high probability $G_p$ contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of $C$ , are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to $p=1$ in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in $G(n,p)$ (corresponding to $G=K_n$ in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least $\tfrac{2n}{3}$ which gets close to the truth.

preprint2018arXiv

Tight bounds on the coefficients of partition functions via stability

Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hard-core model and monomer-dimer model are the independence and matching polynomials respectively. We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markström and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of $q$ -colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least $5$ .

preprint2017arXiv

Extremes of the internal energy of the Potts model on cubic graphs

We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti-ferromagnetic Potts model on cubic graphs at every temperature and for all $q \ge 2$ . This immediately implies corresponding tight bounds on the anti-ferromagnetic Potts partition function. Taking the zero-temperature limit gives new results in extremal combinatorics: the number of $q$ -colorings of a $3$ -regular graph, for any $q \ge 2$ , is maximized by a union of $K_{3,3}$ 's. This proves the $d=3$ case of a conjecture of Galvin and Tetali.

preprint2016arXiv

Ramsey Numbers of Connected Clique Matchings

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 $K_r$ , and that this number of vertices cannot be reduced.

preprint2015arXiv

Partite Saturation Problems

We look at several saturation problems in complete balanced blow-ups of graphs. We let $H[n]$ denote the blow-up of $H$ onto parts of size $n$ and refer to a copy of $H$ in $H[n]$ as 'partite' if it has one vertex in each part of $H[n]$ . We then ask how few edges a subgraph $G$ of $H[n]$ can have such that $G$ has no partite copy of $H$ but such that the addition of any new edge from $H[n]$ creates a partite $H$ . When $H$ is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger. Our main result is to calculate this value for $H=K_4$ when $n$ is large. We also give exact results for paths and stars and show that for $2$ -connected graphs the answer is linear in $n$ whilst for graphs which are not $2$ -connected the answer is quadratic in $n$ . We also investigate a similar problem where $G$ is permitted to contain partite copies of $H$ but we require that the addition of any new edge from $H[n]$ creates an extra partite copy of $H$ . This problem turns out to be much simpler and we attain exact answers for all cliques and trees.

preprint2015arXiv

Triangle-free subgraphs of random graphs

Recently there has been much interest in studying random graph analogues of well known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of $G(n,p)$ with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of $G(n,p)$ with minimum degree at least $\big(\frac{2}{5} + o(1)\big)pn$ is $\mathcal O(p^{-1}n)$ -close to bipartite, and each spanning triangle-free subgraph of $G(n,p)$ with minimum degree at least $(\frac{1}{3}+\varepsilon)pn$ is $\mathcal O(p^{-1}n)$ -close to $r$ -partite for some $r=r(\varepsilon)$ . These are random graph analogues of a result by Andrásfai, Erdős, and Sós [Discrete Math. 8 (1974), 205-218], and a result by Thomassen [Combinatorica 22 (2002), 591--596]. We also show that our results are best possible up to a constant factor.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.