Source author record

Lisa Sauermann

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics econ.TH math.NT math.PR

Catalog footprint

Research overview

9works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

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

Consider $2k-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 alternative $B$ in majority voting (meaning that for every other alternative $B$ there are at least $k$ voters who prefer $A$ over $B$ ). The notion of Condorcet winners has been studied intensively for many decades, yet some basic questions remain open. In this paper, we consider a model where each voter chooses their ranking randomly according to some probability distribution among all rankings. One may then ask about the probability to have a Condorcet winner with these randomly chosen rankings (which, of course, depends on $n$ and $k$ , and the underlying probability distribution on the set of rankings). In the case of the uniform probability distribution over all rankings, which has received a lot of attention and is often referred to as the setting of an "impartial culture", we asymptotically determine the probability of having a Condorcet winner for a fixed number $2k-1$ of voters and $n$ alternatives with $n\to \infty$ . This question has been open for around fifty years. While some authors suggested that the impartial culture should exhibit the lowest possible probability of having a Condorcet winner, in fact the probability can be much smaller for other distributions. We determine, for all values of $n$ and $k$ , the smallest possible probability of having a Condorcet winner (and give an example of a probability distribution over all rankings which achieves this minimum possible probability).

preprint2022arXiv

Polynomials that vanish to high order on most of the hypercube

Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed $k\geq 1$ and $n$ large with respect to $k$ , what is the minimum possible degree of a polynomial $P\in \mathbb{R}[x_1,\dots,x_n]$ with $P(0,\dots,0)\neq 0$ such that $P$ has zeroes of multiplicity at least $k$ at all points in $\{0,1\}^n\setminus \{(0,\dots,0)\}$ ? For $k=1$ , a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals $n$ . In this paper, we solve the problem for all $k\geq 2$ , proving that the answer is $n+2k-3$ . As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in $\mathbb{R}^n$ such that each point in $\{0,1\}^n\setminus \{(0,\dots,0)\}$ is covered by at least $k$ hyperplanes, but the point $(0,\dots,0)$ is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.

preprint2022arXiv

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

In 1989, Rota conjectured that, given $n$ bases $B_1,\dots,B_n$ of the vector space $\mathbb{F}^n$ over some field $\mathbb{F}$ , one can always decompose the multi-set $B_1\cup \dots \cup B_n$ into transversal bases. This conjecture remains wide open despite of a lot of attention. In this paper, we consider the setting of random bases $B_1,\dots,B_n$ . More specifically, our first result shows that Rota's basis conjecture holds with probability $1-o(1)$ as $n\to \infty$ if the bases $B_1,\dots,B_n$ are chosen independently uniformly at random among all bases of $\mathbb{F}_q^n$ for some finite field $\mathbb{F}_q$ (the analogous result is trivially true for an infinite field $\mathbb{F}$ ). In other words, the conjecture is true for almost all choices of bases $B_1,\dots,B_n\subseteq \mathbb{F}_q^n$ . Our second, more general, result concerns random bases $B_1,\dots,B_n\subseteq S^n$ for some given finite subset $S\subseteq \mathbb{F}$ (in other words, bases $B_1,\dots,B_n$ where all vectors have entries in $S$ ). We show that when choosing bases $B_1,\dots,B_n\subseteq S^n$ independently uniformly at random among all bases that are subsets of $S^n$ , then again Rota's basis conjecture holds with probability $1-o(1)$ as $n\to \infty$ .

preprint2022arXiv

Sharp estimates for spanning trees

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 \in V(G)} (d(v)+1)$ spanning trees. This result is tight (for complete graphs), and improves earlier estimates of Alon from 1990 and Kostochka from 1995 by a factor of about $1/n$ (for dense graphs). We additionally show that an analogous bound holds for the weighted spanning tree enumerator of a (nonnegatively) weighted graph as well.

preprint2021arXiv

On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

Given a $k$ -vertex graph $H$ and an integer $n$ , what are the $n$ -vertex graphs with the maximum number of induced copies of $H$ ? This question is closely related to the inducibility problem introduced by Pippenger and Golumbic in 1975, which asks for the maximum possible fraction of $k$ -vertex subsets of an $n$ -vertex graph that induce a copy of $H$ . Huang, Lee and the first author proved that for a random $k$ -vertex graph $H$ , almost surely the $n$ -vertex graphs maximizing the number of induced copies of $H$ are the balanced iterated blow-ups of $H$ . In this paper, we consider the case where the graph $H$ is obtained by deleting a small number of vertices from a random Cayley graph $\widetilde{H}$ of an abelian group. We prove that in this case, almost surely all $n$ -vertex graphs maximizing the number of induced copies of $H$ are balanced iterated blow-ups of $\widetilde{H}$ .

preprint2021arXiv

On the speed of algebraically defined graph classes

The speed of a class of graphs counts the number of graphs on the vertex set $\lbrace 1,\dots, n\rbrace$ inside the class as a function of $n$ . In this paper, we investigate this function for many classes of graphs that naturally arise in discrete geometry, for example intersection graphs of segments or disks in the plane. While upper bounds follow from Warren's theorem (a variant of a theorem of Milnor and Thom), all the previously known lower bounds were obtained from ad hoc constructions for very specific classes. We prove a general theorem giving an essentially tight lower bound for the number of graphs on $\lbrace 1,\dots, n\rbrace$ whose edges are defined using the signs of a given finite list of polynomials, assuming these polynomials satisfy some reasonable conditions. This in particular implies lower bounds for the speed of many different classes of intersection graphs, which essentially match the known upper bounds. Our general result also gives essentially tight lower bounds for counting containment orders of various families of geometric objects, including circle orders and angle orders. Some of the applications presented in this paper are new, whereas others recover results of Alon-Scheinerman, Fox, McDiarmid-Müller and Shi. For the proof of our result we use some tools from algebraic geometry and differential topology.

preprint2020arXiv

A Completion of the Proof of the Edge-statistics Conjecture

For given integers $k$ and $\ell$ with $0<\ell< {k \choose 2}$ , Alon, Hefetz, Krivelevich and Tyomkyn formulated the following conjecture: When sampling a $k$ -vertex subset uniformly at random from a very large graph $G$ , then the probability to have exactly $\ell$ edges within the sampled $k$ -vertex subset is at most $e^{-1}+o_k(1)$ . This conjecture was proved in the case $Ω(k)\leq \ell\leq {k \choose 2}-Ω(k)$ by Kwan, Sudakov and Tran. In this paper, we complete the proof of the conjecture by resolving the remaining cases. We furthermore give nearly tight upper bounds for the probability described above in the case $ω(1)\leq \ell\leq o(k)$ . We also extend some of our results to hypergraphs with bounded edge size.

preprint2020arXiv

An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs

Consider a quadratic polynomial $f\left(ξ_{1},\dots,ξ_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$ , but still poorly understood is the "inverse" question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this paper we prove some results of an algebraic flavour, showing that if $f$ has point probabilities much larger than $1/n$ then it must be close to a quadratic form with low rank. We also give an application to Ramsey graphs, asymptotically answering a question of Kwan, Sudakov and Tran.

preprint2020arXiv

On the size of subsets of $\mathbb{F}_p^{n}$ without $p$ distinct elements summing to zero

Let us fix a prime $p$ . The Erdős-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $\mathbb{Z}^n$ contains $p$ points whose centroid is also a lattice point in $\mathbb{Z}^n$ . For large $n$ , this is essentially equivalent to asking for the maximum size of a subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero. In this paper, we give a new upper bound for this problem for any fixed prime $p\geq 5$ and large $n$ . In particular, we prove that any subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero has size at most $C_p\cdot \left(2\sqrt{p}\right)^n$ , where $C_p$ is a constant only depending on $p$ . For $p$ and $n$ going to infinity, our bound is of the form $p^{(1/2)\cdot (1+o(1))n}$ , whereas all previously known upper bounds were of the form $p^{(1-o(1))n}$ (with $p^n$ being a trivial bound). Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method. This method and its consequences were already applied by Naslund as well as by Fox and the author to prove bounds for the problem studied in this paper. However, using some key new ideas, we significantly improve their bounds.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Lisa Sauermann

Research overview

Is this your work?

9 publications

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

Polynomials that vanish to high order on most of the hypercube

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

Sharp estimates for spanning trees

On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

On the speed of algebraically defined graph classes

A Completion of the Proof of the Edge-statistics Conjecture

An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs

On the size of subsets of $\mathbb{F}_p^{n}$ without $p$ distinct elements summing to zero

See the researcher in context

Building this map preview

Lisa Sauermann

Research overview

Is this your work?

9 publications

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

Polynomials that vanish to high order on most of the hypercube

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

Sharp estimates for spanning trees

On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices

On the speed of algebraically defined graph classes

A Completion of the Proof of the Edge-statistics Conjecture

An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs

On the size of subsets of Fpn\mathbb{F}_p^{n}Fpn​ without ppp distinct elements summing to zero

See the researcher in context

Building this map preview

On the size of subsets of $\mathbb{F}_p^{n}$ without $p$ distinct elements summing to zero