ترغب بنشر مسار تعليمي؟ اضغط هنا

FKN theorem for the multislice, with applications

147   0   0.0 ( 0 )
 نشر من قبل Yuval Filmus
 تاريخ النشر 2018
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English
 تأليف Yuval Filmus




اسأل ChatGPT حول البحث

The Friedgut-Kalai-Naor (FKN) theorem states that if $f$ is a Boolean function on the Boolean cube which is close to degree 1, then $f$ is close to a dictator, a function depending on a single coordinate. The author has extended the theorem to the slice, the subset of the Boolean cube consisting of all vectors with fixed Hamming weight. We extend the theorem further, to the multislice, a multicoloured version of the slice. As an application, we prove a stability version of the edge-isoperimetric inequality for settings of parameters in which the optimal set is a dictator.



قيم البحث

اقرأ أيضاً

The beautiful Beraha-Kahane-Weiss theorem has found many applications within graph theory, allowing for the determination of the limits of root of graph polynomials in settings as vast as chromatic polynomials, network reliability, and generating pol ynomials related to independence and domination. Here we extend the class of functions to which the BKW theorem can be applied, and provide some applications in combinatorics.
In [J. Combin. Theory Ser. B 70 (1997), 2-44] we gave a simplified proof of the Four-Color Theorem. The proof is computer-assisted in the sense that for two lemmas in the article we did not give proofs, and instead asserted that we have verified thos e statements using a computer. Here we give additional details for one of those lemmas, and we include the original computer programs and data as ancillary files accompanying this submission.
68 - Zhengjun Cao , Lihua Liu 2016
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 diff erent 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.
A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence $x$ over a finite alphabet is ultimately periodic if and only if, for some $n$, the number of different factors of length $n$ appearing in $x$ is less than $n+1$. Attem pts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let $dge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of $ZZ^d$ definable by a first order formula in the Presburger arithmetic $<ZZ;<,+>$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse--Hedlund theorem to an arbitrary dimension $d$ and characterize sets of $ZZ^d$ definable in $<ZZ;<,+>$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.
The determination of the weight distribution of linear codes has been a fascinating problem since the very beginning of coding theory. There has been a lot of research on weight enumerators of special cases, such as self-dual codes and codes with sma ll Singletons defect. We propose a new set of linear relations that must be satisfied by the coefficients of the weight distribution. From these relations we are able to derive known identities (in an easier way) for interesting cases, such as extremal codes, Hermitian codes, MDS and NMDS codes. Moreover, we are able to present for the first time the weight distribution of AMDS codes. We also discuss the link between our results and the Pless equations.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا