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.