Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of sum-free triplets of sets
193
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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$.
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$.
As a fundamental research object, the minimum edge dominating set (MEDS) problem is of both theoretical and practical interest. However, determining the size of a MEDS and the number of all MEDSs in a general graph is NP-hard, and it thus makes sense to find special graphs for which the MEDS problem can be exactly solved. In this paper, we study analytically the MEDS problem in the pseudofractal scale-free web and the Sierpinski gasket with the same number of vertices and edges. For both graphs, we obtain exact expressions for the edge domination number, as well as recursive solutions to the number of distinct MEDSs. In the pseudofractal scale-free web, the edge domination number is one-ninth of the number of edges, which is three-fifths of the edge domination number of the Sierpinski gasket. Moreover, the number of all MEDSs in the pseudofractal scale-free web is also less than that corresponding to the Sierpinski gasket. We argue that the difference of the size and number of MEDSs between the two studied graphs lies in the scale-free topology.
We study the problems of bounding the number weak and strong independent sets in $r$-uniform, $d$-regular, $n$-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the first order term for all (fixed) $rge 3$, with $d$ and $n$ going to infinity. In the case of strong independent sets, for $r=3$, we provide an upper bound that is tight up to the second-order term, improving on a result of Ordentlich-Roth (2004). The tightness in the strong independent set case is established by an explicit construction of a $3$-uniform, $d$-regular, cross-edge free, linear hypergraph on $n$ vertices which could be of interest in other contexts. We leave open the general case(s) with some conjectures. Our proofs use the occupancy method introduced by Davies, Jenssen, Perkins, and Roberts (2017).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
