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
    0 references
    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
    0 references
    0 references
    0 references
    0 references

    Identifiers