Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe upper logarithmic density of monochromatic subset sums
142
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 problems 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.
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.
Hindman proved that, whenever the set $mathbb{N}$ of naturals is finitely colored, there must exist non-constant monochromatic solution of the equation $a+b=cd$. In this paper we extend this result for dense subsemigroups of $((0, infty), +)$ to near zero.
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/2rceil}$, 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.
For any subset $A subseteq mathbb{N}$, we define its upper density to be $limsup_{ n rightarrow infty } |A cap { 1, dotsc, n }| / n$. We prove that every $2$-edge-colouring of the complete graph on $mathbb{N}$ contains a monochromatic infinite path, whose vertex set has upper density at least $(9 + sqrt{17})/16 approx 0.82019$. This improves on results of ErdH{o}s and Galvin, and of DeBiasio and McKenney.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
