The existence of exactly \(m\)-coloured complete subgraphs (Q1306417)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The existence of exactly \(m\)-coloured complete subgraphs |
scientific article |
Statements
The existence of exactly \(m\)-coloured complete subgraphs (English)
0 references
17 May 2001
0 references
Let \(P(c,m)\) stand for the following proposition: If the edges of a countably infinite complete graph are exactly \(c\)-coloured, then there exists a countably infinite complete subgraph whose edges are exactly \(m\)-coloured. By exactly \(x\)-coloured, we mean that the colouring map is surjective. \(P(c,1)\) is a standard version of Ramsey's theorem. In [Discrete Math. 126, No. 1-3, 395-398 (1994; Zbl 0790.05058)], M. Erickson observed that \(P(c,2)\) follows from Ramsey's theorem; he produced several counterexamples to \(P(c,m)\) with \(2< m< c\); and he conjectured that \(P(c,m)\) is true only if \(m= 1,2\) or \(c\). In this paper it is proved that for every \(m\geq 3\) there is an integer \(C(m)\) such that \(P(c,m)\) is false whenever \(c\geq C(m)\).
0 references
colouring
0 references
Ramsey's theorem
0 references