اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLarger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
54
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A subset of the integer planar grid $[N] times [N]$ is called corner-free if it contains no triple of the form $(x,y), (x+delta,y), (x,y+delta)$. It is known that such a set has a vanishingly small density, but how large this density can be remains unknown. The best previous construction was based on Behrends large subset of $[N]$ with no $3$-term arithmetic progression. Here we provide the first substantial improvement to this lower bound in decades. Our approach to the problem is based on the theory of communication complexity. In the $3$-players exactly-$N$ problem the players need to decide whether $x+y+z=N$ for inputs $x,y,z$ and fixed $N$. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Despite the basic nature of this problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-$N$ problem. This is also the first significant example where algorithmic ideas in communication complexity bear fruit in additive combinatorics.
قيم البحث
اقرأ أيضاً
An $alpha$-greedy balanced pair in an ordered set $P=(V,leq)$ is a pair $(x,y)$ of elements of $V$ such that the proportion of greedy linear extensions of $P$ that put $x$ before $y$ among all greedy linear extensions is in the real interval $[alpha,
1-alpha]$. We prove that every $N$-free ordered set which is not totally ordered has a $frac{1}{2}$-greedy balanced pair.
In this paper, we study product-free subsets of the free semigroup over a finite alphabet $A$. We prove that the maximum density of a product-free subset of the free semigroup over $A$, with respect to the natural measure that assigns a weight of $|A
|^{-n}$ to each word of length $n$, is precisely $1/2$.
We investigate the relationship between two constructions of maximal comma-free codes described respectively by Eastman and by Scholtz and the notions of Hall sets and Lazard sets introduced in connection with factorizations of free monoids and bases of free Lie algebras.
A subset $A$ of the $k$-dimensional grid ${1,2, cdots, N}^k$ is called $k$-dimensional corner-free if it does not contain a set of points of the form ${ a } cup { a + de_i : 1 leq i leq k }$ for some $a in {1,2, cdots, N}^k$ and $d > 0$, where $e_1,e
_2, cdots, e_k$ is the standard basis of $mathbb{R}^k$. We define the maximum size of a $k$-dimensional corner-free subset of ${1,2, cdots, N}^k$ by $c_k(N)$. In this paper, we show that the number of $k$-dimensional corner-free subsets of the $k$-dimensional grid ${1,2, cdots, N}^k$ is at most $2^{O(c_k(N))}$ for infinitely many values of $N$. Our main tool for the proof is a supersaturation result for $k$-dimensional corners in sets of size $Theta(c_k(N))$ and the hypergraph container method.
We show that, in contrast to the integers setting, almost all even order abelian groups $G$ have exponentially fewer maximal sum-free sets than $2^{mu(G)/2}$, where $mu(G)$ denotes the size of a largest sum-free set in $G$. This confirms a conjecture of Balogh, Liu, Sharifzadeh and Treglown.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
