اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA Note on the Alon-Kleitman Argument for Sum-free Subset Theorem
69
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In 1990, Alon and Kleitman proposed an argument for the sum-free subset problem: every set of n nonzero elements of a finite Abelian group contains a sum-free subset A of size |A|>frac{2}{7}n. In this note, we show that the argument confused two different randomness. It applies only to the finite Abelian group G = (Z/pZ)^s where p is a prime. For the general case, the problem remains open.
قيم البحث
اقرأ أيضاً
The r-th power of a graph modifies a graph by connecting every vertex pair within distance r. This paper gives a generalization of the Alon-Boppana Theorem for the r-th power of graphs, including irregular graphs. This leads to a generalized notion o
f Ramanujan graphs, those for which the powered graph has a spectral gap matching the derived Alon-Boppana bound. In particular, we show that certain graphs that are not good expanders due to local irregularities, such as Erdos-Renyi random graphs, become almost Ramanujan once powered. A different generalization of Ramanujan graphs can also be obtained from the nonbacktracking operator. We next argue that the powering operator gives a more robust notion than the latter: Sparse Erdos-Renyi random graphs with an adversary modifying a subgraph of log(n)^c$ vertices are still almost Ramanujan in the powered sense, but not in the nonbacktracking sense. As an application, this gives robust community testing for different block models.
In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as t
he maximum input number $rm{mx}_X$ and the sum of all input numbers $Sigma_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,rm{mx}_X,Sigma_X$ for which dense Subset Sum is in time $tilde{O}(n)$. For notational convenience we assume without loss of generality that $t ge rm{mx}_X$ (as larger numbers can be ignored) and $t le Sigma_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP91], we show that Subset Sum is in near-linear time $tilde{O}(n)$ if $t gg rm{mx}_X Sigma_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t ll rm{mx}_X Sigma_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds.
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$.
In the picture-hanging puzzle we are to hang a picture so that the string loops around $n$ nails and the removal of any nail results in a fall of the picture. We show that the length of a sequence representing an element in the free group with $n$ ge
nerators that corresponds to a solution of the picture-hanging puzzle must be at least $n2^{sqrt{log_2 n}}$. In other words, this is a lower bound on the length of a sequence representing a non-trivial element in the free group with $n$ generators such that if we replace any of the generators by the identity the sequence becomes trivial.
Hellys theorem is a classical result concerning the intersection patterns of convex sets in $mathbb{R}^d$. Two important generalizations are the colorful version and the fractional version. Recently, B{a}r{a}ny et al. combined the two, obtaining a co
lorful fractional Helly theorem. In this paper, we give an improved version of their result.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
