اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAnticoncentration versus the number of subset sums
280
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $vec{w} = (w_1,dots, w_n) in mathbb{R}^{n}$. We show that for any $n^{-2}leepsilonle 1$, if [#{vec{xi} in {0,1}^{n}: langle vec{xi}, vec{w} rangle = tau} ge 2^{-epsilon n}cdot 2^{n}] for some $tau in mathbb{R}$, then [#{langle vec{xi}, vec{w} rangle : vec{xi} in {0,1}^{n}} le 2^{O(sqrt{epsilon}n)}.] This exponentially improves the $epsilon$ dependence in a recent result of Nederlof, Pawlewicz, Swennenhuis, and Wk{e}grzycki and leads to a similar improvement in the parameterized (by the number of bins) runtime of bin packing.
قيم البحث
اقرأ أيضاً
We develop novel techniques which allow us to prove a diverse range of results relating to subset sums and complete sequences of positive integers, including solutions to several longstanding open problems. These include: solutions to the three probl
ems of Burr and ErdH{o}s on Ramsey complete sequences, for which ErdH{o}s later offered a combined total of $350; analogous results for the new notion of density complete sequences; the solution to a conjecture of Alon and ErdH{o}s on the minimum number of colors needed to color the positive integers less than $n$ so that $n$ cannot be written as a monochromatic sum; the exact determination of an extremal function introduced by ErdH{o}s and Graham on sets of integers avoiding a given subset sum; and, answering a question reiterated by several authors, a homogeneous strengthening of a seminal result of Szemeredi and Vu on long arithmetic progressions in subset sums.
We show that in any two-coloring of the positive integers there is a color for which the set of positive integers that can be represented as a sum of distinct elements with this color has upper logarithmic density at least $(2+sqrt{3})/4$ and this is
best possible. This answers a forty-year-old question of ErdH{o}s.
We settle the existence of certain anti-magic cubes using combinatorial block designs and graph decompositions to align a handful of small examples.
Let $G$ be an additive abelian group and $Ssubset G$ a subset. Let $Sigma(S)$ denote the set of group elements which can be expressed as a sum of a nonempty subset of $S$. We say $S$ is zero-sum free if $0 otin Sigma(S)$. It was conjectured by R.B.~
Eggleton and P.~Erd{o}s in 1972 and proved by W.~Gao et. al. in 2008 that $|Sigma(S)|geq 19$ provided that $S$ is a zero-sum free subset of an abelian group $G$ with $|S|=6$. In this paper, we determined the structure of zero-sum free set $S$ where $|S|=6$ and $|Sigma(S)|=19$.
Let $f(n,r)$ denote the maximum number of colourings of $A subseteq lbrace 1,ldots,nrbrace$ with $r$ colours such that each colour class is sum-free. Here, a sum is a subset $lbrace x,y,zrbrace$ such that $x+y=z$. We show that $f(n,2) = 2^{lceil n/2r
ceil}$, and describe the extremal subsets. Further, using linear optimisation, we asymptotically determine the logarithm of $f(n,r)$ for $r leq 5$. Similar results were obtained by H`an and Jimenez in the setting of finite abelian groups.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
