Matthew Jenssen

activity

20152026

most citedOn the average size of independent sets in triangle-free graphs

41 citations · 162 across the 24 of their papers we have counts for

collaborators

32 papers

math.CO2026

The replica symmetric solution for hypergraph independent sets in the critical regime

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We prove a variational formula for the logarithmic asymptotics of a non-existence probability in a broad class of combinatorial problems such as avoiding cliques in random graphs a…

math.PR2026

On the self-intersection time of non-backtracking random walks

Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen +4

We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ \geq 3$ we show that the expected self-intersection time i…

math-ph2026

Uniqueness, analyticity and mixing for Gibbs point processes via spectral gaps

Andreas Göbel, Matthew Jenssen, Marcus Michelen +3

A Gibbs point process models particles interacting in the continuum through a potential. Among the most classical examples is the hard-sphere model, where given an activity paramet…

math.PR2026

A simple proof of rapid mixing on random regular graphs beyond uniqueness

Andreas Göbel, Matthew Jenssen, Marcus Michelen +3

A recent breakthrough of Chen, Chen, Chen, Yin, and Zhang shows rapid mixing for Glauber dynamics for the hard-core model on random regular graphs beyond the tree uniqueness thresh…

math.CO2026

Non-existence probabilities and lower tails in the critical regime via Belief Propagation

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of…

math.PR2024★ 1 cited

Lower tails for triangles inside the critical window

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We study the probability that the random graph $G (n, p)$ is triangle-free. When $p = o (n^{- 1/2})$ or $p = ω (n^{- 1/2})$ the asymptotics of the logarithm of this probability are known…

cs.DS2024

Sampling and counting triangle-free graphs near the critical density

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We study the following combinatorial counting and sampling problems: can we efficiently sample from the Erdős-Rényi random graph $G (n, p)$ conditioned on triangle-freeness? Can we e…

math.CO2023

On the evolution of structure in triangle-free graphs

Matthew Jenssen, Will Perkins, Aditya Potukuchi

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 cont…

math.CO2023

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem

Matthew Jenssen, Viresh Patel, Guus Regts

We prove that for any graph $G$ of maximum degree at most $Δ$ , the zeros of its chromatic polynomial $χ_{G} (x)$ (in $C$ ) lie inside the disc of radius $5.94Δ$ centered at $…

cs.DS2022

Quasipolynomial-time algorithms for Gibbs point processes

Matthew Jenssen, Marcus Michelen, Mohan Ravichandran

We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of a Gibbs point process interacting via a finite-range stable potential. Thi…

math.CO2022★ 1 cited

A robust Corrádi--Hajnal Theorem

Peter Allen, Julia Böttcher, Jan Corsten +5

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 ex…

math.PR2022

The least singular value of a random symmetric matrix

Marcelo Campos, Matthew Jenssen, Marcus Michelen +1

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}(σ…

cs.DS2021

Approximately counting independent sets in bipartite graphs via graph containers

Matthew Jenssen, Will Perkins, Aditya Potukuchi

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…

math.PR2021★ 1 cited

The singularity probability of a random symmetric matrix is exponentially small

Marcelo Campos, Matthew Jenssen, Marcus Michelen +1

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…

math.CO2021

Independent sets of a given size and structure in the hypercube

Matthew Jenssen, Will Perkins, Aditya Potukuchi

We determine the asymptotics of the number of independent sets of size $⌊ β 2^{d - 1} ⌋$ in the discrete hypercube $Q_{d} = {0, 1}^{d}$ for any fixed $β \in [0, 1]$ as $d \to \…

math.PR2020

Singularity of random symmetric matrices revisited

Marcelo Campos, Matthew Jenssen, Marcus Michelen +1

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 lo g n)^{1/2})$ , which repre…

math.CO2020

Homomorphisms from the torus

Matthew Jenssen, Peter Keevash

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus $Z_{m}^{n}$ , where $m$ is even, to any fixed graph: we…

math.PR2020★ 2 cited

Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs

Tyler Helmuth, Matthew Jenssen, Will Perkins

For $Δ \geq 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 dete…

math.CO2020

A proof of the Upper Matching Conjecture for large graphs

Ewan Davies, Matthew Jenssen, Will Perkins

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 enoug…

math.CO2019

Distinct degrees in induced subgraphs

Matthew Jenssen, Peter Keevash, Eoin Long +1

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 hom…

math.CO2019★ 23 cited

Independent sets in the hypercube revisited

Matthew Jenssen, Will Perkins

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…

math.CO2018★ 2 cited

The multicolour size-Ramsey number of powers of paths

Jie Han, Matthew Jenssen, Yoshiharu Kohayakawa +2

Given a positive integer $s$ , a graph $G$ is $s$ -Ramsey for a graph $H$ , denoted $G \to (H)_{s}$ , if every $s$ -colouring of the edges of $G$ contains a monochromatic copy of $…

cs.DS2018★ 2 cited

Algorithms for #BIS-hard problems on expander graphs

Matthew Jenssen, Peter Keevash, Will Perkins

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 m…

math.MG2018

On kissing numbers and spherical codes in high dimensions

Matthew Jenssen, Felix Joos, Will Perkins

We prove a lower bound of $Ω (d^{3/2} \cdot (2/ 3)^{d})$ on the kissing number in dimension $d$ . This improves the classical lower bound of Chabauty, Shannon, and Wyner by a lin…