Institution | University of Birmingham |
---|---|

Position | Lecturer in Probability and Modern Statistics |

m.jenssen@bham.ac.uk |

- with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe
`@article{campos2020singularity, title={Singularity of random symmetric matrices revisited}, author={Campos, Marcelo and Michelen, Marcus and Jenssen, Matthew and Sahasrabudhe, Julian}, journal={arXiv preprint arXiv:2011.03013}, year={2020} }`

Let $M_n$ be drawn uniformly from all $\pm 1$ symmetric $n \times n$ matrices. We show that the probability that $M_n$ is singular is at most $\exp(-c(n\log n)^{1/2})$, which represents a natural barrier in recent approaches to this problem. In addition to improving on the best-known previous bound of Campos, Mattos, Morris and Morrison of $\exp(-c n^{1/2})$ on the singularity probability, our method is different and considerably simpler.

- with Peter Keevash
`@article{jenssen2020homomorphisms, title={Homomorphisms from the torus}, author={Jenssen, Matthew and Keevash, Peter}, journal={arXiv preprint arXiv:2009.08315}, year={2020} }`

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus $\mathbb{Z}_m^n$, where $m$ is even, to any fixed graph: we show that the corresponding probability distribution on such homomorphisms is close to a distribution defined constructively as a certain random perturbation of some dominant phase. This has several consequences, including solutions (in a strong form) to conjectures of Engbers and Galvin and a conjecture of Kahn and Park. Special cases include sharp asymptotics for the number of independent sets and the number of proper $q$-colourings of $\mathbb{Z}_m^n$ (so in particular, the discrete hypercube). We give further applications to the study of height functions and (generalised) rank functions on the discrete hypercube and disprove a conjecture of Kahn and Lawrenz. For the proof we combine methods from statistical physics, entropy and graph containers and exploit isoperimetric and algebraic properties of the torus.

**Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs**with Tyler Helmuth and Will Perkins*Submitted*`@article{helmuth2020finite, title={Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs}, author={Helmuth, Tyler and Jenssen, Matthew and Perkins, Will}, journal={arXiv preprint arXiv:2006.11580}, year={2020} }`

For Δ≥5 and q large as a function of Δ, we give a detailed picture of the phase transition of the random cluster model on random Δ-regular graphs. In particular, we determine the limiting distribution of the weights of the ordered and disordered phases at criticality and prove exponential decay of correlations away from criticality. Our techniques are based on using polymer models and the cluster expansion to control deviations from the ordered and disordered ground states. These techniques also yield efficient approximate counting and sampling algorithms for the Potts and random cluster models on random Δ-regular graphs at all temperatures when q is large. Our algorithms apply more generally to Δ-regular graphs satisfying a small set expansion condition.

- with Ewan Davies and Will Perkins
*Submitted*`@article{davies2020proof, title={A proof of the {U}pper {M}atching {C}onjecture for large graphs}, author={Davies, Ewan and Jenssen, Matthew and Perkins, Will}, journal={arXiv preprint arXiv:2004.06695}, year={2020} }`

We prove that the `Upper Matching Conjecture' of Friedland, Krop, and Markström and the analogous conjecture of Kahn for independent sets in regular graphs hold for all large enough graphs as a function of the degree. That is, for every $d$ and every large enough $n$ divisible by $2d$, a union of $n/(2d)$ copies of the complete $d$-regular bipartite graph maximizes the number of independent sets and matchings of size $k$ for each $k$ over all $d$-regular graphs on $n$ vertices. To prove this we utilize the cluster expansion for the canonical ensemble of a statistical physics spin model, and we give some further applications of this method to maximizing and minimizing the number of independent sets and matchings of a given size in regular graphs of a given minimum girth.

- with Peter Keevash, Eoin Long and Liana Yepremyan
*Proceedings of the AMS, 148, (2020), 3835-3846*`@article{jenssen2020distinct, title={Distinct degrees in induced subgraphs}, author={Jenssen, Matthew and Keevash, Peter and Long, Eoin and Yepremyan, Liana}, journal={Proceedings of the American Mathematical Society}, volume={148}, pages={3835--3846}, year={2020} }`

An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An $N$-vertex graph is called $C$-Ramsey if it has no homogeneous set of size $C \log N$. A theorem of Bukh and Sudakov, solving a conjecture of Erdős, Faudree and Sós, shows that any $C$-Ramsey $N$-vertex graph contains an induced subgraph with $\Omega_C(N^{1/2})$ distinct degrees. We improve this to $\Omega_C(N^{2/3})$, which is tight up to the constant factor. We also show that any $N$-vertex graph with $N>(k−1)(n−1)$ and $n\geq n_0(k)=Ω(k^9)$ either contains a homogeneous set of order $n$ or an induced subgraph with $k$ distinct degrees. The lower bound on $N$ here is sharp, as shown by an appropriate Turán graph, and confirms a conjecture of Narayanan and Tomon.

- with Will Perkins
*Journal of the LMS (to appear)*`@article{jenssen2020independent, title={Independent sets in the hypercube revisited}, author={Jenssen, Matthew and Perkins, Will}, journal={Journal of the London Mathematical Society}, year={2020}, publisher={Wiley Online Library} }`

We revisit Sapozhenko's classic proof on the asymptotics of the number of independent sets in the discrete hypercube $\{0,1\}^d$ and Galvin's follow-up work on weighted independent sets. We combine Sapozhenko's graph container methods with the cluster expansion and abstract polymer models, two tools from statistical physics, to obtain considerably sharper asymptotics and detailed probabilistic information about the typical structure of (weighted) independent sets in the hypercube. These results refine those of Korshunov and Sapozhenko and Galvin, and answer several questions of Galvin.

- with Peter Keevash and Will Perkins
*SIAM Journal on Computing, 49, (2020), 681–710*`@article{jenssen2020algorithms, title={Algorithms for $\#${BIS}-hard problems on expander graphs}, author={Jenssen, Matthew and Keevash, Peter and Perkins, Will}, journal={SIAM Journal on Computing}, volume={49}, number={4}, pages={681--710}, year={2020}, publisher={SIAM} }`

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) $\Delta$-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite $\Delta$-regular tree. We also find efficient counting and sampling algorithms for proper $q$-colorings of random $\Delta$-regular bipartite graphs when $q$ is sufficiently small as a function of $\Delta$.

- with Felix Joos and Will Perkins
*Advances in Mathematics, 335, (2018), 307– 321*`@article{jenssen2018kissing, title={On kissing numbers and spherical codes in high dimensions}, author={Jenssen, Matthew and Joos, Felix and Perkins, Will}, journal={Advances in Mathematics}, volume={335}, pages={307--321}, year={2018}, publisher={Elsevier} }`

We prove a lower bound of $\Omega(d^{3/2}\cdot(2/\sqrt{3})^d)$ on the kissing number in dimension $d$. This improves the classical lower bound of Chabauty, Shannon, and Wyner by a linear factor in the dimension. We obtain a similar linear factor improvement to the best known lower bound on the maximal size of a spherical code of acute angle $\theta$ in high dimensions.

- with Felix Joos and Will Perkins
*Forum of Mathematics, Sigma, Vol. 7, (2019)*`@inproceedings{jenssen2019hard, title={On the hard sphere model and sphere packings in high dimensions}, author={Jenssen, Matthew and Joos, Felix and Perkins, Will}, booktitle={Forum of Mathematics, Sigma}, volume={7}, year={2019}, organization={Cambridge University Press} }`

We provide a statistical physics based proof of the $\Omega(d \cdot 2^{-d})$ lower bound on the sphere packing density of $\mathbb{R}^d$ by showing that the expected packing density of a random configuration from the hard sphere model is at least $(1+o_d(1)) \log(2/\sqrt{3}) d \cdot 2^{-d}$ when the ratio of the fugacity parameter to the volume covered by a single sphere is at least $3^{-d/2}$. Such a bound on the sphere packing density was first achieved by Rogers, with subsequent improvements to the leading constant by Davenport and Rogers, Ball, Vance, and Venkatesh. While our technique does not achieve the same constant as these other proofs, we do obtain additional geometric information: we prove the first non-trivial lower bound on the entropy of sphere packings of density $\Theta(d \cdot 2^{-d})$, a measure of how plentiful such packings are.

- with Jie Han, Yoshiharu Kohayakawa, Guilherme Oliveira Mota and Barnaby Roberts
*Journal of Combinatorial Theory, Series B, 145, (2020), 359–375*`@article{han2020multicolour, title={The multicolour size-{R}amsey number of powers of paths}, author={Han, Jie and Jenssen, Matthew and Kohayakawa, Yoshiharu and Mota, Guilherme Oliveira and Roberts, Barnaby}, journal={Journal of Combinatorial Theory, Series B}, volume={145}, pages={359--375}, year={2020}, publisher={Elsevier} }`

Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $G\rightarrow (H)_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number $\hat r_s(H)$ of a graph $H$ is defined to be $\hat r_s(H)=\min\{|E(G)|\colon G\rightarrow (H)_s\}$. We prove that, for all positive integers $k$ and $s$, we have $\hat r_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$.

- with Dennis Clemens, Yoshiharu Kohayakawa, Natasha Morrison, Guilherme Oliveira Mota, Damian Reding, Barnaby Roberts
*Journal of Graph Theory, 91, (2019), 290–299*`@article{clemens2019size, title={The size-{R}amsey number of powers of paths}, author={Clemens, Dennis and Jenssen, Matthew and Kohayakawa, Yoshiharu and Morrison, Natasha and Mota, Guilherme Oliveira and Reding, Damian and Roberts, Barnaby}, journal={Journal of Graph Theory}, volume={91}, number={3}, pages={290--299}, year={2019}, publisher={Wiley Online Library} }`

Given graphs $G$ and $H$ and a positive integer $q$, say that $G$ is $q$-Ramsey for $H$, denoted $G\rightarrow (H)_q$, if every $q$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The size-Ramsey number $\hat r(H)$ of a graph $H$ is defined to be $\hat r(H)=\min\{|E(G)|\colon G\rightarrow (H)_2\}$. Answering a question of Conlon, we prove that, for every fixed $k$, we have $\hat r(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$ (i.e. the graph with vertex set $V(P_n)$ and all edges $\{u,v\}$ such that the distance between $u$ and $v$ in $P_n$ is at most $k$). Our proof is probabilistic, but can also be made constructive.

- with Ewan Davies, Will Perkins and Barnaby Roberts
*Journal of Combinatorial Theory, Series A, 160, (2018), 1–30*`@article{davies2018tight, title={Tight bounds on the coefficients of partition functions via stability}, author={Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, journal={Journal of Combinatorial Theory, Series A}, volume={160}, pages={1--30}, year={2018}, publisher={Elsevier} }`

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$. - with Ewan Davies, Will Perkins and Barnaby Roberts
*Random Structures & Algorithms, 53, (2018), 59–75*`@article{davies2018extremes, title={Extremes of the internal energy of the {P}otts model on cubic graphs}, author={Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, journal={Random Structures \& Algorithms}, volume={53}, number={1}, pages={59--75}, year={2018}, publisher={Wiley Online Library} }`

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\geq2$. 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\geq2$, is maximized by a union of $K_{3,3}$'s. This proves the $d=3$ case of a conjecture of Galvin and Tetali. - with Jozef Skokan
*Advances in Mathematics (to appear)*`@article{jenssen2020exact, title={Exact {R}amsey numbers of odd cycles via nonlinear optimisation}, author={Jenssen, Matthew and Skokan, Jozef}, journal={Advances in Mathematics}, pages={107444}, year={2020}, publisher={Elsevier} } }`

For a graph $G$, the $k$-colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$-colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$. Let $C_n$ denote the cycle on $n$ vertices. We show that for fixed $k\geq2$ and $n$ odd and sufficiently large, $$ R_k(C_n)=2^{k-1}(n-1)+1. $$ This resolves a conjecture of Bondy and Erd\H{o}s for large $n$. The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. This allows us to prove a stability-type generalisation of the above and establish a correspondence between extremal $k$-colourings for this problem and perfect matchings in the $k$-dimensional hypercube $Q_k$.

- with Ewan Davies, Will Perkins and Barnaby Roberts
*Proceedings of the AMS, 146, (2018), 111–124*`@article{davies2018average, title={On the average size of independent sets in triangle-free graphs}, author={Davies, Ewan and Jenssen, Matthew and Perkins, Will and Roberts, Barnaby}, journal={Proceedings of the American Mathematical Society}, volume={146}, number={1}, pages={111--124}, year={2018} }`

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_d(1)) \frac{\log d}{d}n$. 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 \left[\left(\frac{1}{2}+o_d(1) \right) \frac{\log^2 d}{d}n \right]$. 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 $\lambda^{|I|}$, for a fugacity parameter $\lambda>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 $\lambda =O_d(1)$.

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. - with Ewan Davies and Barnaby Roberts
*European Journal of Combinatorics, 63, (2017), 124–133*`@article{davies2017multicolour, title={Multicolour {R}amsey numbers of paths and even cycles}, author={Davies, Ewan and Jenssen, Matthew and Roberts, Barnaby}, journal={European Journal of Combinatorics}, volume={63}, pages={124--133}, year={2017}, publisher={Elsevier} }`

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)\leq R_k(P_n)\leq R_k(C_n)\leq kn+o(n)$. The upper bound was recently improved by Sárközy who showed that $R_k(C_n)\leq\left(k-\frac{k}{16k^3+1}\right)n+o(n)$. Here we show $R_k(C_n) \leq (k-\frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.

- with Peter Keevash and Will Perkins
*Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms 49 (SODA 2019), 2235-2247*`@inproceedings{jenssen2019algorithms, title={Algorithms for\#{BIS}-hard problems on expander graphs}, author={Jenssen, Matthew and Keevash, Peter and Perkins, Will}, booktitle={Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms}, pages={2235--2247}, year={2019}, organization={SIAM} }`

We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) $\Delta$-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite $\Delta$-regular tree.

*Electronic Notes in Discrete Mathematics, 49, (2015), 377–381*`@article{jenssen2015multicolour, title={The multicolour {R}amsey number of a long odd cycle}, author={Jenssen, Matthew}, journal={Electronic Notes in Discrete Mathematics}, volume={49}, pages={377--381}, year={2015}, publisher={Elsevier} }`

For a graph $G$, the $k$-colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$-colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$. Bondy and Erdős conjectured that for an odd cycle $C_n$ on $n>3$ vertices, $$ R_k(C_n)=2^{k-1}(n-1)+1\, . $$ This is known to hold when $k=2$ and $n>3$, and when $k=3$ and $n$ is large. We show that this conjecture holds asymptotically for $k\geq 4$, proving that for $n$ odd, $$ R_k(C_n)=2^{k-1}n+o(n) \text{ as } n\to\infty \, . $$ The proof uses the regularity lemma to relate this problem in Ramsey theory to one in convex optimisation, allowing analytic methods to be exploited. Our analysis leads us to a new class of lower bound constructions for this problem, which naturally arise from perfect matchings in the $k$-dimensional hypercube. Progress towards a resolution of the conjecture for large $n$ is also discussed.

- with Arielle Fujiwara, Joseph Gibson, Daniel Montealegre, Vadim Ponomarenko
*Communications in Algebra, 44 (8), (2016), 3407–3421*`@article{fujiwara2016arithmetic, title={Arithmetic of Congruence Monoids}, author={Fujiwara, Arielle and Gibson, Joseph and Jenssen, Matthew O and Montealegre, Daniel and Ponomarenko, Vadim and Tenzer, Ari}, journal={Communications in Algebra}, volume={44}, number={8}, pages={3407--3421}, year={2016}, publisher={Taylor \& Francis} }`

- with Daniel Montealegre, Vadim Ponomarenko
*American Mathematical Monthly, 120 (4), (2013), 322–328*`@article{jenssen2013irreducible, title={Irreducible factorization lengths and the elasticity problem within $\mathbb{N}$}, author={Jenssen, Matthew and Montealegre, Daniel and Ponomarenko, Vadim}, journal={The American Mathematical Monthly}, volume={120}, number={4}, pages={322--328}, year={2013}, publisher={Taylor \& Francis} }`