No Arabic abstract
For any subset $A subseteq mathbb{N}$, we define its upper density to be $limsup_{ n rightarrow infty } |A cap { 1, dotsc, n }| / n$. We prove that every $2$-edge-colouring of the complete graph on $mathbb{N}$ contains a monochromatic infinite path, whose vertex set has upper density at least $(9 + sqrt{17})/16 approx 0.82019$. This improves on results of ErdH{o}s and Galvin, and of DeBiasio and McKenney.
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.
We investigate the number of 4-edge paths in graphs with a fixed number of vertices and edges. An asymptotically sharp upper bound is given to this quantity. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k-edge stars.
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
N. Hindman, I. Leader and D. Strauss proved that it is consistent that there is a finite colouring of $mathbb R$ so that no infinite sumset $X+X={x+y:x,yin X}$ is monochromatic. Our aim in this paper is to prove a consistency result in the opposite direction: we show that, under certain set-theoretic assumptions, for any $c:mathbb Rto r$ with $r$ finite there is an infinite $Xsubseteq mathbb R$ so that $c$ is constant on $X+X$.
Gyarfas conjectured in 2011 that every $r$-edge-colored $K_n$ contains a monochromatic component of bounded (perhaps three) diameter on at least $n/(r-1)$ vertices. Letzter proved this conjecture with diameter four. In this note we improve the result in the case of $r=3$: We show that in every $3$-edge-coloring of $K_n$ either there is a monochromatic component of diameter at most three on at least $n/2$ vertices or every color class is spanning and has diameter at most four.