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

Showing math.COShow all

18 papers · 1 filter

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.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.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 $…

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.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.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.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 $…

math.CO2017

The size-Ramsey number of powers of paths

Dennis Clemens, Matthew Jenssen, Yoshiharu Kohayakawa +4

Given graphs $G$ and $H$ and a positive integer $q$ say that $G$ is $q$ -Ramsey for $H$ , denoted $G \to (H)_{q}$ , if every $q$ -colouring of the edges of $G$ contains a monochro…

math.CO2017★ 3 cited

Tight bounds on the coefficients of partition functions via stability

Ewan Davies, Matthew Jenssen, Will Perkins +1

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. Fo…

math.CO2016★ 15 cited

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

Ewan Davies, Matthew Jenssen, Will Perkins +1

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…

math.CO2016

Exact Ramsey numbers of odd cycles via nonlinear optimisation

Matthew Jenssen, Jozef Skokan

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…

math.CO2016★ 41 cited

On the average size of independent sets in triangle-free graphs

Ewan Davies, Matthew Jenssen, Will Perkins +1

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

math.CO2016★ 11 cited

Multicolour Ramsey numbers of paths and even cycles

Ewan Davies, Matthew Jenssen, Barnaby Roberts

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 k n + o (n)$ . The upper bound was…

math.CO2015★ 28 cited

Independent Sets, Matchings, and Occupancy Fractions

Ewan Davies, Matthew Jenssen, Will Perkins +1

We prove tight upper bounds on the logarithmic derivative of the independence and matching polynomials of d-regular graphs. For independent sets, this theorem is a strengthening of…