Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShape of the asymptotic maximum sum-free sets in integer lattice grids
90
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We determine the shape of all sum-free sets in ${1,dots,n}^2$ of size close to the maximum $frac{3}{5}n^2$, solving a problem of Elsholtz and Rackham. We show that all such asymptotic maximum sum-free sets lie completely in the stripe $frac{4}{5}n-o(n)le x+ylefrac{8}{5}n+ o(n)$. We also determine for any positive integer $p$ the maximum size of a subset $Asubseteq {1,dots,n}^2$ which forbids the triple $(x,y,z)$ satisfying $px+py=z$.
rate research
Read More
We count the ordered sum-free triplets of subsets in the group $mathbb{Z}/pmathbb{Z}$, i.e., the triplets $(A,B,C)$ of sets $A,B,C subset mathbb{Z}/pmathbb{Z}$ for which the equation $a+b=c$ has no solution with $ain A$, $b in B$ and $c in C$. Our main theorem improves on a recent result by Semchankau, Shabanov, and Shkredov using a different and simpler method. Our proof relates previous results on the number of independent sets of regular graphs by Kahn, Perarnau and Perkins, and Csikvari to produce explicit estimates on smaller order terms. We also obtain estimates for the number of sum-free triplets of subsets in a general abelian group.
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.
A subset of vertices is a {it maximum independent set} if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a {it maximum dissociation set} if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. Zito [J. Graph Theory {bf 15} (1991) 207--221] proved that the maximum number of maximum independent sets of a tree of order $n$ is $2^{frac{n-3}{2}}$ if $n$ is odd, and $2^{frac{n-2}{2}}+1$ if $n$ is even and also characterized all extremal trees with the most maximum independent sets, which solved a question posed by Wilf. Inspired by the results of Zito, in this paper, by establishing four structure theorems and a result of $k$-K{o}nig-Egerv{a}ry graph, we show that the maximum number of maximum dissociation sets in a tree of order $n$ is begin{center} $left{ begin{array}{ll} 3^{frac{n}{3}-1}+frac{n}{3}+1, & hbox{if $nequiv0pmod{3}$;} 3^{frac{n-1}{3}-1}+1, & hbox{if $nequiv1pmod{3}$;} 3^{frac{n-2}{3}-1}, & hbox{if $nequiv2pmod{3}$,} end{array} right.$ end{center} and also give complete structural descriptions of all extremal trees on which these maxima are achieved.
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$.
A tri-colored sum-free set in an abelian group $H$ is a collection of ordered triples in $H^3$, ${(a_i,b_i,c_i)}_{i=1}^m$, such that the equation $a_i+b_j+c_k=0$ holds if and only if $i=j=k$. Using a variant of the lemma introduced by Croot, Lev, and Pach in their breakthrough work on arithmetic-progression-free sets, we prove that the size of any tri-colored sum-free set in $mathbb{F}_2^n$ is bounded above by $6 {n choose lfloor n/3 rfloor}$. This upper bound is tight, up to a factor subexponential in $n$: there exist tri-colored sum-free sets in $mathbb{F}_2^n$ of size greater than ${n choose lfloor n/3 rfloor} cdot 2^{-sqrt{16 n / 3}}$ for all sufficiently large $n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
