The size-Ramsey number of 3-uniform tight paths

Ramsey’s Theorem is one of the most famous results in extremal combinatorics, which sparked a very intensive line of research on the existence of well-behaved substructures in various kinds of combinatorial objects. In its simplest form, Ramsey’s Theorem asserts that for every positive integer $n$ there exists $R(n)$ such that the complete $R(n)$-vertex graph with edges colored with two colors arbitrarily must contain a set of $n$ vertices such that all edges joining these vertices have the same color. Despite an enormous amount of work that led to a large number of extensions and generalizations, determining the smallest possible value of $R(n)$ exactly remains to be very challenging and the value is only known for $n\in\{1,2,3,4\}$. Indeed, a quote attributed to Erdős says that if vastly more powerful aliens threatened to obliterate the Earth unless humans could compute $R(n)$, then we should marshall all computers and mathematicians if their demand concerned $n=5$ but launch a preemptive attack for $n=6$.

This paper concerns a setting where the host graph need not be complete. The size-Ramsey number of a graph $G$ is the smallest integer $m$ that there exists an $m$-edge graph $H$ such that any $2$-edge-coloring of $H$ contains a monochromatic copy of $G$. Estimating the size-Ramsey number of a particular graph $G$ is challenging even for simple graphs. For example, in the early 1980s, Erdős asked whether the size-Ramsey number of a path is linear in its length; the question was answered positively by Beck using a probabilistic argument in 1983 and a constructive proof was given by Alon and Chung in 1988. The main result of the paper is an extension to the setting of $3$-uniform hypergraphs: the size-Ramsey number of the tight $3$-uniform path is linear in its length.