Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the maximum number of integer colourings with forbidden monochromatic sums
70
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $f(n,r)$ denote the maximum number of colourings of $A subseteq lbrace 1,ldots,nrbrace$ with $r$ colours such that each colour class is sum-free. Here, a sum is a subset $lbrace x,y,zrbrace$ such that $x+y=z$. We show that $f(n,2) = 2^{lceil n/2rceil}$, and describe the extremal subsets. Further, using linear optimisation, we asymptotically determine the logarithm of $f(n,r)$ for $r leq 5$. Similar results were obtained by H`an and Jimenez in the setting of finite abelian groups.
rate research
Read More
Let $mathbf{k} := (k_1,dots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;mathbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;mathbf{k})$ to denote the maximum of $F(G;mathbf{k})$ over all graphs $G$ on $n$ vertices. This problem was first considered by ErdH{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. We prove that, for every $mathbf{k}$ and $n$, there is a complete multipartite graph $G$ on $n$ vertices with $F(G;mathbf{k}) = F(n;mathbf{k})$. Also, for every $mathbf{k}$ we construct a finite optimisation problem whose maximum is equal to the limit of $log_2 F(n;mathbf{k})/{nchoose 2}$ as $n$ tends to infinity. Our final result is a stability theorem for complete multipartite graphs $G$, describing the asymptotic structure of such $G$ with $F(G;mathbf{k}) = F(n;mathbf{k}) cdot 2^{o(n^2)}$ in terms of solutions to the optimisation problem.
We study the mixed Ramsey number maxR(n,K_m,K_r), defined as the maximum number of colours in an edge-colouring of the complete graph K_n, such that K_n has no monochromatic complete subgraph on m vertices and no rainbow complete subgraph on r vertices. Improving an upper bound of Axenovich and Iverson, we show that maxR(n,K_m,K_4) <= n^{3/2}sqrt{2m} for all m >= 3. Further, we discuss a possible way to improve their lower bound on maxR(n,K_4,K_4) based on incidence graphs of finite projective planes.
We show that for any $2$-local colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most~$3$ disjoint monochromatic paths. And, we can cover almost all vertices of any complete or balanced complete bipartite $r$-locally coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path almost exactly: Every $2$-local colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices.
We show that in any two-coloring of the positive integers there is a color for which the set of positive integers that can be represented as a sum of distinct elements with this color has upper logarithmic density at least $(2+sqrt{3})/4$ and this is best possible. This answers a forty-year-old question of ErdH{o}s.
Hindman proved that, whenever the set $mathbb{N}$ of naturals is finitely colored, there must exist non-constant monochromatic solution of the equation $a+b=cd$. In this paper we extend this result for dense subsemigroups of $((0, infty), +)$ to near zero.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
