Ramsey numbers for tournaments (Q5941503)
From MaRDI portal
scientific article; zbMATH DE number 1635696
Language | Label | Description | Also known as |
---|---|---|---|
English | Ramsey numbers for tournaments |
scientific article; zbMATH DE number 1635696 |
Statements
Ramsey numbers for tournaments (English)
0 references
20 August 2001
0 references
Let \(D_1,\dots, D_k\) be acyclic digraphs (possibly several are isomorphic). The authors define the \(k\)-color Ramsey number \(r(D_1,\dots, D_k)\) as the largest integer \(r\) for which there exists a tournament \(T= (V,A)\) on \(r\) vertices and a \(k\)-coloring \(\phi: A\to \{1,\dots, k\}\) of its arc set such that no \(D_i\) is a subdigraph of \(T\) in color \(i\) \((1\leq i\leq k)\). The authors discuss recursive techniques for computing \(r(D_1,\dots, D_k)\) in the case when some of the \(D_i\)'s are paths or stars. In particular, solving a problem of \textit{A. Bialostocki} and \textit{P. Dierker} [Congr. Numerantium 47, 119-123 (1985; Zbl 0622.05046)], they prove that \(r(D_1,D_2)= r(D_1)* r(D_2)\) holds if \(D_1\) is transitive and \(D_2\) is \(S_n\), the star with all arcs directed out of the center. The main result of the paper is an asymptotic formula for \(r(D_1,\dots, D_k,S_n)\), where the digraphs \(D_1,\dots, D_k\) are fixed arbitrary acyclic digraphs and \(n\to\infty\).
0 references
acyclic digraphs
0 references
Ramsey number
0 references
tournament
0 references