Papers (see also arXiv)
- with Marcelo Campos, Marcus Michelen and Julian SahasrabudheSubmitted
@article{campos2023new, title={A new lower bound for sphere packing}, author={Campos, Marcelo and Michelen, Marcus and Jenssen, Matthew and Sahasrabudhe, Julian}, journal={arXiv preprint arXiv:2312.10026}, year={2023} }
We show there exists a packing of identical spheres in $\mathbb{R}^d$ with density at least \[ (1-o(1))\frac{d \log d}{2^{d+1}}\, , \] as $d\to\infty$. This improves upon previous bounds for general $d$ by a factor of order $\log d$ and is the first asymptotically growing improvement to Rogers' bound from 1947.
- with Will Perkins and Aditya PotukuchiSubmitted
@article{jenssen2023evolution, title={On the evolution of structure in triangle-free graphs}, author={Jenssen, Matthew and Perkins, Will and Potukuchi, Aditya}, journal={arXiv preprint arXiv:2312.09202}, year={2023} }
We study the typical structure and the number of triangle-free graphs with $n$ vertices and $m$ edges where $m$ is large enough so that a typical triangle-free graph has a cut containing nearly all of its edges, but may not be bipartite. Erd\H{o}s, Kleitman, and Rothschild showed that almost every triangle-free graph is bipartite. Osthus, Prömel, and Taraz later showed that for $m \ge (1+\epsilon)\frac{\sqrt{3}}{4}n^{3/2}\sqrt{\log n}$, almost every triangle-free graph on $n$ vertices and $m$ edges is bipartite. Here we give a precise characterization of the distribution of edges within each part of the max cut of a uniformly chosen triangle-free graph $G$ on $n$ vertices and $m$ edges, for a larger range of densities with $m=\Theta(n^{3/2} \sqrt{\log n})$. Using this characterization, we describe the evolution of the structure of typical triangle-free graphs as the density changes. We show that as the number of edges decreases below $\frac{\sqrt{3}}{4} n^{3/2}\sqrt{\log n}$, the following structural changes occur in $G$: -Isolated edges, then trees, then more complex subgraphs emerge as `defect edges', edges within parts of a max cut of $G$. The distribution of defect edges is first that of independent Erdős–Rényi random graphs, then that of independent exponential random graphs, conditioned on a small maximum degree and no triangles. -There is a sharp threshold for $3$-colorability at $m \sim \frac{\sqrt{2}}{4} n^{3/2}\sqrt{\log n}$ and a sharp threshold between $4$-colorability and unbounded chromatic number at $m\sim\frac{1}{4}n^{3/2}\sqrt{\log n}$. -Giant components emerge in the defect edges at $m\sim\frac{1}{4} n^{3/2}\sqrt{\log n}$. We use this to prove asymptotic formulas for the number of triangle-free graphs at these densities. We also prove analogous results for $G(n,p)$ conditioned on triangle-freeness.
- with Viresh Patel and Guus RegtsSubmitted
@article{jenssen2023improved, title={Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem}, author={Jenssen, Matthew and Patel, Viresh and Regts, Guus}, journal={arXiv preprint arXiv:2309.10928}, year={2023} }
We prove that for any graph $G$ of maximum degree at most $\Delta$, the zeros of its chromatic polynomial $\chi_G(x)$ (in $\mathbb{C}$) lie inside the disc of radius $5.94 \Delta$ centered at $0$. This improves on the previously best known bound of approximately $6.91\Delta$. We also obtain improved bounds for graphs of high girth. We prove that for every $g$ there is a constant $K_g$ such that for any graph $G$ of maximum degree at most $\Delta$ and girth at least $g$, the zeros of its chromatic polynomial $\chi_G(x)$ lie inside the disc of radius $K_g \Delta$ centered at $0$, where $K_g$ is the solution to a certain optimization problem. In particular, $K_g < 5$ when $g \geq 5$ and $K_g < 4$ when $g \geq 25$ and $K_g$ tends to approximately $3.86$ as $g \to \infty$. Key to the proof is a classical theorem of Whitney which allows us to relate the chromatic polynomial of a graph $G$ to the generating function of so-called broken-circuit-free forests in $G$. We also establish a zero-free disc for the generating function of all forests in $G$ (aka the partition function of the arboreal gas) which may be of independent interest.
- with Marcus Michelen and Mohan RavichandranCombinatorics, Probability and Computing, (2023), 1-15
@article{jenssen2022quasipolynomial, title={Quasipolynomial-time algorithms for Gibbs point processes}, author={Jenssen, Matthew and Michelen, Marcus and Ravichandran, Mohan}, journal={arXiv preprint arXiv:2209.10453}, year={2022} }
We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of a Gibbs point process interacting via a stable potential. This result holds for all activities $\lambda$ for which the partition function satisfies a zero-free assumption in a neighborhood of the interval $[0,\lambda]$. As a corollary, for all finite-range stable potentials we obtain a quasipolynomial-time determinsitic algorithm for all $\lambda < 1/(e^{B + 1} \hat C_\phi)$ where $\hat C_\phi$ is a temperedness parameter and $B$ is the stability constant of $\phi$. In the special case of a repulsive potential such as the hard-sphere gas we improve the range of activity by a factor of at least $e^2$ and obtain a quasipolynomial-time deterministic approximation algorithm for all $\lambda < e/\Delta_\phi$, where $\Delta_\phi$ is the potential-weighted connective constant of the potential $\phi$. Our algorithm approximates coefficients of the cluster expansion of the partition function and uses the interpolation method of Barvinok to extend this approximation throughout the zero-free region.
- with Peter Allen, Julia Böttcher, Jan Corsten, Ewan Davies, Patrick Morris, Barnaby Roberts and Jozef SkokanSubmitted
@article{allen2022robust, title={A robust Corr\'adi--Hajnal Theorem}, author={Allen, Peter and B\"ottcher, Julia and Corsten, Jan and Davies, Ewan and Jenssen, Matthew and Morris, Patrick and Roberts, Barnaby and Skokan, Jozef}, journal={arXiv preprint arXiv:2209.01116}, year={2022} }
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 $\delta(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.
- with Marcelo Campos, Marcus Michelen and Julian SahasrabudheForum of Mathematics, Pi (to appear)
@article{campos2022least, title={The least singular value of a random symmetric matrix}, author={Campos, Marcelo and Michelen, Marcus and Jenssen, Matthew and Sahasrabudhe, Julian}, journal={arXiv preprint arXiv:2203.06141}, year={2022} }
Let $A$ be a $n \times n$ symmetric matrix with $(A_{i,j})_{i\leq j} $, independent and identically distributed according to a subgaussian distribution. We show that $$\mathbb P(\sigma_{\min}(A) \leq \epsilon/\sqrt{n}) \leq C \epsilon + e^{-cn},$$ where $\sigma_{\min}(A)$ denotes the least singular value of $A$ and the constants $C,c>0 $ depend only on the distribution of the entries of $A$. This result confirms a folklore conjecture and is best possible up to the dependence of the constants on the distribution of $A_{i,j}$. Along the way, we prove that the probability $A$ has a repeated eigenvalue is $e^{-\Omega(n)}$, thus confirming a conjecture of Nguyen, Tao and Vu.
- with Marcelo Campos, Marcus Michelen and Julian SahasrabudheJournal of the AMS (to appear)
@article{campos2021singularity, title={The singularity probability of a random symmetric matrix is exponentially small}, author={Campos, Marcelo and Michelen, Marcus and Jenssen, Matthew and Sahasrabudhe, Julian}, journal={arXiv preprint arXiv:2105.11384}, year={2021} }
Let $A$ be drawn uniformly at random from the set of all $n\times n$ symmetric matrices with entries in $\{-1,1\}$. We show that \[ \mathbb{P}( \det(A) = 0 ) \leq e^{-cn},\] where $c>0$ is an absolute constant, thereby resolving a well-known conjecture.
- with Will Perkins and Aditya PotukuchiRandom Structures & Algorithms, 63, (2023), 215-241
@article{jenssen2023approximately, title={Approximately counting independent sets in bipartite graphs via graph containers}, author={Jenssen, Matthew and Perkins, Will and Potukuchi, Aditya}, journal={Random Structures \& Algorithms}, year={2023}, publisher={Wiley Online Library} }
By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. Our first algorithm applies to $d$-regular, bipartite graphs satisfying a weak expansion condition: when $d$ is constant, and the graph is a bipartite $\Omega( \log^2 d/d)$-expander, we obtain an FPTAS for the number of independent sets. Previously such a result for $d>5$ was known only for graphs satisfying the much stronger expansion conditions of random bipartite graphs. The algorithm also applies to weighted independent sets: for a $d$-regular, bipartite $\alpha$-expander, with $\alpha>0$ fixed, we give an FPTAS for the hard-core model partition function at fugacity $\lambda=\Omega(\log d / d^{1/4})$. Finally we present an algorithm that applies to all $d$-regular, bipartite graphs, runs in time $\exp\left( O\left( n \cdot \frac{ \log^3 d }{d } \right) \right)$, and outputs a $(1 + o(1))$-approximation to the number of independent sets.
- with Marcelo Campos, Marcus Michelen and Julian SahasrabudheProceedings of the AMS, 150, (2022), 3147-3159
@article{campos2022singularity, title={Singularity of random symmetric matrices revisited}, author={Campos, Marcelo and Jenssen, Matthew and Michelen, Marcus and Sahasrabudhe, Julian}, journal={Proceedings of the American Mathematical Society}, volume={150}, number={7}, pages={3147--3159}, year={2022} }
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 Will Perkins and Aditya PotukuchiCombinatorics, Probability and Computing, 31, (2022), 702-720
@article{jenssen2021independent, title={Independent sets of a given size and structure in the hypercube}, author={Jenssen, Matthew and Perkins, Will and Potukuchi, Aditya}, journal={Combinatorics, Probability and Computing}, pages={1--19}, year={2021}, publisher={Cambridge University Press} }
We determine the asymptotics of the number of independent sets of size $\lfloor \beta 2^{d-1} \rfloor$ in the discrete hypercube $Q_d = \{0,1\}^d$ for any fixed $\beta \in [0,1]$ as $d \to \infty$, extending a result of Galvin for $\beta \in [1-1/\sqrt{2},1]$. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $\lambda>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.
- with Peter KeevashAdvances in Mathematics, 430, (2023), 109-212
@article{jenssen2023homomorphisms, title={Homomorphisms from the torus}, author={Jenssen, Matthew and Keevash, Peter}, journal={Advances in Mathematics}, volume={430}, pages={109--212}, year={2023}, publisher={Elsevier} }
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 graphswith Tyler Helmuth and Will PerkinsAnnales de l'Institut Henri Poincaré (B) Probabilités et Statistiques, 59 (2), (2023), 817-848
@inproceedings{helmuth2023finite, 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}, booktitle={Annales de l'Institut Henri Poincare (B) Probabilites et statistiques}, volume={59}, number={2}, pages={817--848}, year={2023}, organization={Institut Henri Poincar{\'e}} }
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 PerkinsJournal of Combinatorial Theory, Series B, 151, (2021), 393-416
@article{davies2021proof, title={A proof of the {U}pper {M}atching {C}onjecture for large graphs}, author={Davies, Ewan and Jenssen, Matthew and Perkins, Will}, journal={Journal of Combinatorial Theory, Series B}, volume={151}, pages={393--416}, year={2021}, publisher={Elsevier} }
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 YepremyanProceedings 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 PerkinsJournal of the LMS, 102, (2020), 645-669.
@article{jenssen2020independent, title={Independent sets in the hypercube revisited}, author={Jenssen, Matthew and Perkins, Will}, journal={Journal of the London Mathematical Society}, volume={102}, number={2}, pages={645--669}, 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 PerkinsSIAM 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 PerkinsAdvances 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 PerkinsForum 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 RobertsJournal 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 RobertsJournal 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 RobertsJournal 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 RobertsRandom 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 SkokanAdvances in Mathematics, 376, (2021), 107444
@article{jenssen2021exact, title={Exact Ramsey numbers of odd cycles via nonlinear optimisation}, author={Jenssen, Matthew and Skokan, Jozef}, journal={Advances in Mathematics}, volume={376}, pages={107444}, year={2021}, 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 RobertsProceedings 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 RobertsEuropean 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.
Conference publications
- with Will Perkins and Aditya PotukuchiProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), 499-516
@inbook{doi:10.1137/1.9781611977073.24, author = {Matthew Jenssen and Aditya Potukuchi and Will Perkins}, title = {Approximately counting independent sets in bipartite graphs via graph containers}, booktitle = {Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)}, chapter = {}, pages = {499-516}, doi = {10.1137/1.9781611977073.24}, URL = {https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.24}, }
By implementing algorithmic versions of Sapozhenko's graph container methods, we give new algorithms for approximating the number of independent sets in bipartite graphs. The first algorithm applies to $d$-regular, bipartite graphs satisfying a weak expansion condition: when $d$ is constant, and the graph is a $\Omega( \log^3 d/d)$-bipartite expander, we obtain an FPTAS for the number of independent sets. Previously such a result for $d>5$ was known only for graphs satisfying the much stronger expansion conditions of random graphs. The second algorithm applies to all $d$-regular, bipartite graphs, runs in time $\exp\left( O\left( n \cdot \frac{ \log^4 d }{d } \right) \right)$, and outputs a $(1 + o(1))$-approximation to the number of independent sets.
- with Peter Keevash and Will PerkinsProceedings 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.
Other publications
- 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 PonomarenkoCommunications 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 PonomarenkoAmerican 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} }