Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three

Andrzej Ruciński ; Eliza Jackowska ; Joanna Polcyn

The electronic journal of combinatorics, Tome 24 (2017) no. 3

Résumé

Let $P$ denote a 3-uniform hypergraph consisting of 7 vertices $a,b,c,d,e,f,g$ and 3 edges $\{a,b,c\}, \{c,d,e\},$ and $\{e,f,g\}$. It is known that the $r$-colored Ramsey number for $P$ is $R(P;r)=r+6$ for $r=2,3$, and that $R(P;r)\le 3r$ for all $r\ge3$. The latter result follows by a standard application of the Turán number $\mathrm{ex}_3(n;P)$, which was determined to be $\binom{n-1}2$ in our previous work. We have also shown that the full star is the only extremal 3-graph for $P$. In this paper, we perform a subtle analysis of the Turán numbers for $P$ under some additional restrictions. Most importantly, we determine the largest number of edges in an $n$-vertex $P$-free 3-graph which is not a star. These Turán-type results, in turn, allow us to confirm the formula $R(P;r)=r+6$ for $r\in\{4,5,6,7\}$.

Détail

DOI : 10.37236/7119

Classification : 05C65
Mots-clés : Ramsey numbers, Turán numbers, hypergraphs