Generalizations of some Ramsey-type theorems for matchings (Q5946750)
From MaRDI portal
scientific article; zbMATH DE number 1659497
Language | Label | Description | Also known as |
---|---|---|---|
English | Generalizations of some Ramsey-type theorems for matchings |
scientific article; zbMATH DE number 1659497 |
Statements
Generalizations of some Ramsey-type theorems for matchings (English)
0 references
27 February 2002
0 references
Let \(\text{RM}(G)\) be the smallest integer \(r\) for which every colouring of the edges of the complete graph \(K_r\) contains a copy of the graph \(G\) which is either monochromatic (all edges the same colour) or rainbow (no two edges the same colour). Note that \(\text{RM}(G)\) is well defined only when \(G\) is acyclic. For the remainder of this review, \(G\) will consist of \(n\) independent edges, that is, it will be an \(n\)-matching. The authors show that \(\text{RM}(G)=n^2-n+2\), which equals the standard Ramsey number for \(G\) in \((n-1)\)-colourings of complete graphs. Secondly, they show that provided \(n\geq 3\), every 3-colouring of \(K_{3n-1}\) contains a copy of \(G\) which is either monochromatic or contains each of the three distinct colours. Thirdly they show a related result for 5-colourings of \(K_{3n-1}\). The graph \(K_{3n-1}\) is of interest because it is the smallest complete graph which when 2-coloured must contain a monochromatic copy of \(G\). Finally, they suggest possible generalisations of their results to hypergraphs.
0 references
Ramsey number
0 references
matching
0 references
hypermatching
0 references