Mehtaab Sawhney

activity

20152026

most citedThe number of independent sets in an irregular graph

14 citations · 74 across the 75 of their papers we have counts for

collaborators

Showing 2021Show all

15 papers · 1 filter

math.CO2021

Enumerating Matroids and Linear Spaces

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(c n + o (n))^{n^{2} /6}$ , where $c=e^{…

cs.DS2021

Online Edge Coloring via Tree Recurrences and Correlation Decay

Janardhan Kulkarni, Yang P. Liu, Ashwin Sah +2

We give an online algorithm that with high probability computes a $(\frac{e}{e - 1} + o (1)) Δ$ edge coloring on a graph $G$ with maximum degree $Δ = ω (lo g n)$ under online…

math.CO2021

Note on random Latin squares and the triangle removal process

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

This is a companion note to the paper "Almost all Steiner triple systems have perfect matchings (arXiv:1611.02246). That paper contains several general lemmas about random Steiner…

cs.DS2021

Approximate counting and sampling via local central limit theorems

Vishesh Jain, Will Perkins, Ashwin Sah +1

We give an FPTAS for computing the number of matchings of size $k$ in a graph $G$ of maximum degree $Δ$ on $n$ vertices, for all $k \leq (1 - δ) m^{*} (G)$ , where $δ > 0$ is fixed and $m^*(…

math.CO2021★ 3 cited

Non-classical polynomials and the inverse theorem

Aaron Berger, Ashwin Sah, Mehtaab Sawhney +1

In this note we characterize when non-classical polynomials are necessary in the inverse theorem for the Gowers $U^{k}$ -norm. We give a brief deduction of the fact that a bounded fun…

math.PR2021

Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

Asaf Ferber, Vishesh Jain, Ashwin Sah +1

Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric ${\pm 1}$ -matrix is irreducible. This addr…

math.CO2021

Friendly bisections of random graphs

Asaf Ferber, Matthew Kwan, Bhargav Narayanan +2

Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph $G (n, 1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its…

math.CO2021

Large deviations in random Latin squares

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

In this note, we study large deviations of the number $N$ of intercalates ( $2 \times 2$ combinatorial subsquares which are themselves Latin squares) in a random $n \times n$ …

math.PR2021

Singularity of the k-core of a random graph

Asaf Ferber, Matthew Kwan, Ashwin Sah +1

Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of "low-degree dependencies'' such as isolated vertices and…

math.CO2021★ 3 cited

Majority Dynamics: The Power of One

Ashwin Sah, Mehtaab Sawhney

Consider $n = ℓ + m$ individuals, where $ℓ \leq m$ , with $ℓ$ individuals holding an opinion $A$ and $m$ holding an opinion $B$ . Suppose that the individuals communicate via an u…

cs.DS2021

A Gaussian fixed point random walk

Yang P. Liu, Ashwin Sah, Mehtaab Sawhney

In this note, we design a discrete random walk on the real line which takes steps $0, \pm 1$ (and one with steps in ${\pm 1, 2}$ ) where at least $96%$ of the signs are $\pm 1$ i…

math.PR2021

Rank deficiency of random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $M_{n}$ be a random $n \times n$ matrix with i.i.d. $Bernoulli (1/2)$ entries. We show that for fixed $k \geq 1$ , \[\lim_{n\to \infty}\frac{1}{n}\log_2\mathbb{P}[\text{corank…

math.CO2021★ 11 cited

Popular differences for matrix patterns

Aaron Berger, Ashwin Sah, Mehtaab Sawhney +1

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_{1}$ , $M_{2}$ be $k \times k$ integer matrices, $G$ …

math.MG2021

The cylindrical width of transitive sets

Ashwin Sah, Mehtaab Sawhney, Yufei Zhao

We show that for every $1 \leq k \leq d / (lo g d)^{C}$ , every finite transitive set of unit vectors in $R^{d}$ lies within distance $O (1/ lo g (d / k))$ of some codimension $…

math.CO2021

Anticoncentration versus the number of subset sums

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $w = (w_{1}, \dots, w_{n}) \in R^{n}$ . We show that for any $n^{- 2} \leq ε \leq 1$ , if \[\#\{\vecξ \in \{0,1\}^{n}: \langle \vecξ, \vec{w} \rangle = τ\} \ge 2^{-εn}\cdot 2…