Zobrazeno 1 - 10
of 32
pro vyhledávání: '"Ashwin Sah"'
Publikováno v:
Discrete Analysis (2021)
Patterns without a popular difference, Discrete Analysis 2021:8, 30 pp. Szemerédi's theorem states that for every $\delta>0$ and every positive integer $k$ there exists $N$ such that every subset $A\subset[N]$ of size at least $\delta N$ contains an
Externí odkaz:
https://doaj.org/article/3403373ae3914da493fe3d4d393dca90
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::397f1d45b6ea239b4a711fe96fa865b6
https://doi.org/10.1137/1.9781611977554.ch152
https://doi.org/10.1137/1.9781611977554.ch152
Publikováno v:
The Annals of Applied Probability. 32
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f556c6bbde7f416fd300aeccf4aa997c
https://doi.org/10.1214/22-aap1784
https://doi.org/10.1214/22-aap1784
Publikováno v:
Israel Journal of Mathematics. 244:589-620
We examine the behavior of the number of k-term arithmetic progressions in a random subset of ℤ/nℤ. We prove that if a set is chosen by including each element of ℤ/nℤ independently with constant probability p, then the resulting distribution
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::04df5239d7ea6a66d26075057fda5e52
https://doi.org/10.1007/s11856-021-2180-7
https://doi.org/10.1007/s11856-021-2180-7
Autor:
Ashwin Sah
Publikováno v:
Combinatorica. 41:99-126
Extending results of Linial (1984) and Aigner (1985), we prove a uniform lower bound on the balance constant of a poset $P$ of width $2$. This constant is defined as $\delta(P) = \max_{(x, y)\in P^2}\min\{\mathbb{P}(x\prec y), \mathbb{P}(y\prec x)\}$
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2bb9946220d827e4d43051998dfd41fc
https://doi.org/10.1007/s00493-020-4091-3
https://doi.org/10.1007/s00493-020-4091-3
Publikováno v:
Archiv der Mathematik. 115:53-66
We generalize results of Alladi, Dawsey, and Sweeting and Woo for Chebotarev densities to general densities of sets of primes. We show that if K is a number field and S is any set of prime ideals with natural density $$\delta (S)$$ within the primes,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7c217bc29f21a9fbbfaedd59fc63bee5
https://doi.org/10.1007/s00013-020-01458-z
https://doi.org/10.1007/s00013-020-01458-z
Let $X$ be a random vector valued in $\mathbb{R}^{m}$ such that $\|X\|_{2} \le 1$ almost surely. For every $k\ge 3$, we show that there exists a sigma algebra $\mathcal{F}$ generated by a partition of $\mathbb{R}^{m}$ into $k$ sets such that \[\|\ope
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::78c9b26f3e6197f27dbdd9bade1978df
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 $(cn+o(n))^{n^2/6}$, where $c=e^{\sqrt 3/2-3}(1+\sqrt 3)/2$. This is the final piece of the puzzle for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f34ff7fcfaf959b62304538780786c0e
http://arxiv.org/abs/2112.03788
http://arxiv.org/abs/2112.03788
We give an FPTAS for computing the number of matchings of size $k$ in a graph $G$ of maximum degree $\Delta$ on $n$ vertices, for all $k \le (1-\delta)m^*(G)$, where $\delta>0$ is fixed and $m^*(G)$ is the matching number of $G$, and an FPTAS for the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4e58a7ab62e74e08e96f1fb1e3978f27
http://arxiv.org/abs/2108.01161
http://arxiv.org/abs/2108.01161
Publikováno v:
STOC
We present a randomized algorithm which takes as input an undirected graph G on n vertices with maximum degree Δ, and a number of colors k ≥ (8/3 + oΔ(1))Δ, and returns – in expected time O(nΔ2logk) – a proper k-coloring of G distributed pe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::81475111fc3af9264590ce58cc975162
https://doi.org/10.1145/3406325.3451012
https://doi.org/10.1145/3406325.3451012