Lisa Sauermann

activity

20142026

most citedCombinatorial anti-concentration inequalities, with applications

13 citations · 53 across the 33 of their papers we have counts for

collaborators

40 papers

math.CO2026

Poset dimension and maximum comparability degree

Carla Groenland, Richard Montgomery, Rajko Nenadov +1

In 1986, Füredi and Kahn showed that the dimension $dim (P)$ of any finite poset $P$ satisfies $dim (P) = O (d lo g^{2} d)$ , where $d$ is the maximum degree of the comparability graph…

math.CO2026

Permanents of random matrices over finite fields

Zach Hunter, Matthew Kwan, Lisa Sauermann

Fix a finite field $F_{q}$ and let $A \in F_{q}^{n \times n}$ be a uniformly random $n \times n$ matrix over $F_{q}$ . The asymptotic distribution of the determinant…

math.CO2026

On Graham's rearrangement conjecture

Huy Tuan Pham, Lisa Sauermann

Graham conjectured in 1971 that for any prime $p$ , any subset $S \subseteq Z_{p} ∖ {0}$ admits an ordering $s_{1}, s_{2}, \dots, s_{∣ S ∣}$ where all partial sums $s_1, s_1+s…

math.CO2025

Disproof of the Odd Hadwiger Conjecture

Marcus Kühn, Lisa Sauermann, Raphael Steiner +1

We prove that there exist graphs which do not contain $K_{t}$ as an odd minor and whose chromatic number is at least $(\frac{3}{2} - o (1)) t$ . This disproves, in a strong form, the odd Had…

math.PR2025

On random matrices with large corank

Zach Hunter, Matthew Kwan, Lisa Sauermann +1

Let $1 \leq k \leq n$ and $M$ be a random $n \times n$ matrix with independent uniformly random ${\pm 1}$ -entries. We show that there exists an absolute constant $c > 0$ such that \[\…

math.PR2025

Exponential anticoncentration of the permanent

Zach Hunter, Matthew Kwan, Lisa Sauermann

Let $A \in R^{n \times n}$ be a random matrix with independent entries, and suppose that the entries are "uniformly anticoncentrated" in the sense that there is a constant $\…

math.CO2025

Asymptotically-tight packing and covering with transversal bases in Rota's basis conjecture

Richard Montgomery, Lisa Sauermann

In 1989, Rota conjectured that, given any $n$ bases $B_{1}, \dots, B_{n}$ of a vector space of dimension $n$ , or more generally a matroid of rank $n$ , it is possible to rearrange these i…

math.CO2025

Algebraic aspects of the polynomial Littlewood-Offord problem

Zhihan Jin, Matthew Kwan, Lisa Sauermann +1

Consider a degree- $d$ polynomial $f (ξ_{1}, \dots, ξ_{n})$ of independent Rademacher random variables $ξ_{1}, \dots, ξ_{n}$ . To what extent can $f (ξ_{1}, \dots, ξ_{n})$ concentrate on a single point?…

math.NT2024

Improving Behrend's construction: Sets without arithmetic progressions in integers and over finite fields

Christian Elsholtz, Zach Hunter, Laura Proske +1

We prove new lower bounds on the maximum size of subsets $A \subseteq {1, \dots, N}$ or $A \subseteq F_{p}^{n}$ not containing three-term arithmetic progressions. In the setting…

math.CO2024

New lower bounds for three-term progression free sets in $F_{p}^{n}$

Christian Elsholtz, Laura Proske, Lisa Sauermann

We prove new lower bounds on the maximum size of sets $A \subseteq F_{p}^{n}$ or $A \subseteq Z_{m}^{n}$ not containing three-term arithmetic progressions (consisting of th…

math.CO2023★ 2 cited

Resolution of the quadratic Littlewood--Offord problem

Matthew Kwan, Lisa Sauermann

Consider a quadratic polynomial $Q (ξ_{1}, \dots, ξ_{n})$ of independent Rademacher random variables $ξ_{1}, \dots, ξ_{n}$ . To what extent can $Q (ξ_{1}, \dots, ξ_{n})$ concentrate on a si…

math.CO2023

A Sharp Ramsey Theorem for Ordered Hypergraph Matchings

Lisa Sauermann, Dmitrii Zakharov

We prove essentially sharp bounds for Ramsey numbers of ordered hypergraph matchings, inroduced recently by Dudek, Grytczuk, and Ruciński. Namely, for any $r \geq 2$ and $n \geq 2$ ,…

math.CO2023★ 3 cited

Essentially tight bounds for rainbow cycles in proper edge-colourings

Noga Alon, Matija Bucić, Lisa Sauermann +2

An edge-coloured graph is said to be rainbow if no colour appears more than once. Extremal problems involving rainbow objects have been a focus of much research over the last decad…

math.CO2023

On the Erdős--Ginzburg--Ziv Problem in large dimension

Lisa Sauermann, Dmitrii Zakharov

The Erdős--Ginzburg--Ziv Problem is a classical extremal problem in discrete geometry. Given $m$ and $n$ , the problem asks about the smallest number $s$ such that among any $s$ poi…

math.CO2023★ 1 cited

Unit and distinct distances in typical norms

Noga Alon, Matija Bucić, Lisa Sauermann

Erdős' unit distance problem and Erdős' distinct distances problem are among the most classical and well-known open problems in discrete mathematics. They ask for the maximum numbe…

math.NT2022

Sárközy's Theorem in Various Finite Field Settings

Anqi Li, Lisa Sauermann

In this paper, we strengthen a result by Green about an analogue of Sarkozy's theorem in the setting of polynomial rings $F_{q} [x]$ . In the integer setting, for a given poly…

math.CO2022

Sharp bounds for rainbow matchings in hypergraphs

Cosmin Pohoata, Lisa Sauermann, Dmitrii Zakharov

Suppose we are given matchings $M_{1}, ...., M_{N}$ of size $t$ in some $r$ -uniform hypergraph, and let us think of each matching having a different color. How large does $N$ need to be…

math.CO2022★ 3 cited

Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture

Matthew Kwan, Ashwin Sah, Lisa Sauermann +1

An $n$ -vertex graph is called $C$ -Ramsey if it has no clique or independent set of size $C lo g_{2} n$ (i.e., if it has near-optimal Ramsey behavior). In this paper, we study edge-sta…

math.CO2022

Rota's basis conjecture holds for random bases of vector spaces

Lisa Sauermann

In 1989, Rota conjectured that, given $n$ bases $B_{1}, \dots, B_{n}$ of the vector space $F^{n}$ over some field $F$ , one can always decompose the multi-set $B_1\cup \do…

econ.TH2022★ 1 cited

On the probability of a Condorcet winner among a large number of alternatives

Lisa Sauermann

Consider $2 k - 1$ voters, each of which has a preference ranking between $n$ given alternatives. An alternative $A$ is called a Condorcet winner, if it wins against every other alter…

math.CO2021

Finding solutions with distinct variables to systems of linear equations over $F_{p}$

Lisa Sauermann

Let us fix a prime $p$ and a homogeneous system of $m$ linear equations $a_{j, 1} x_{1} + \dots + a_{j, k} x_{k} = 0$ for $j = 1, \dots, m$ with coefficients $a_{j, i} \in F_{p}$ . Suppose that $…

math.CO2021★ 1 cited

Sharp estimates for spanning trees

Steven Klee, Bhargav Narayanan, Lisa Sauermann

We prove the following sharp estimate for the number of spanning trees of a graph in terms of its vertex-degrees: a simple graph $G$ on $n$ vertices has at most $(1/n^{2}) \prod_{v…

cs.IT2020

List-decodability with large radius for Reed-Solomon codes

Asaf Ferber, Matthew Kwan, Lisa Sauermann

List-decodability of Reed-Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focu…

math.CO2020

Singularity of sparse random matrices: simple proofs

Asaf Ferber, Matthew Kwan, Lisa Sauermann

Consider a random $n \times n$ zero-one matrix with "density" $p$ , sampled according to one of the following two models: either every entry is independently taken to be one with pro…

Poset dimension and maximum comparability degree

Permanents of random matrices over finite fields

On Graham's rearrangement conjecture

Disproof of the Odd Hadwiger Conjecture

On random matrices with large corank

Exponential anticoncentration of the permanent

Asymptotically-tight packing and covering with transversal bases in Rota's basis conjecture

Algebraic aspects of the polynomial Littlewood-Offord problem

Improving Behrend's construction: Sets without arithmetic progressions in integers and over finite fields

New lower bounds for three-term progression free sets in Fpn​

Resolution of the quadratic Littlewood--Offord problem

A Sharp Ramsey Theorem for Ordered Hypergraph Matchings

Essentially tight bounds for rainbow cycles in proper edge-colourings

On the Erdős--Ginzburg--Ziv Problem in large dimension

Unit and distinct distances in typical norms

Sárközy's Theorem in Various Finite Field Settings

Sharp bounds for rainbow matchings in hypergraphs

Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture

Rota's basis conjecture holds for random bases of vector spaces

On the probability of a Condorcet winner among a large number of alternatives

Finding solutions with distinct variables to systems of linear equations over Fp​

Sharp estimates for spanning trees

List-decodability with large radius for Reed-Solomon codes

Singularity of sparse random matrices: simple proofs

New lower bounds for three-term progression free sets in $F_{p}^{n}$

Finding solutions with distinct variables to systems of linear equations over $F_{p}$