Anti-Ramsey theorems

Erdős, Pál and Simonovits, Miklós and T. Sós, Vera (1975) Anti-Ramsey theorems. In: Infinite and finite sets : To Paul Erdős on his 60th birthday. North-Holland Publishing Company, Amsterdam, pp. 633-643. ISBN 0720428149

Preview

Text 1975-05.pdf Download (1MB) | Preview

Abstract

Let c be an edge-colouring of the complete n-graph Kn with m colours. A totally multicoloured (TMC) subgraph of Kn (with respect to c) is a graph G⊆Kn such that no two edges of G have the same colour. Let H be a graph with less than n vertices. If m is sufficiently large then there is in Kn a TMC subgraph isomorphic to H. Let f(n,H) denote the maximal number m such that there is an m-colouring of Kn without a TMC-subgraph isomorphic to H. Put d=min(χ(H−e),e∈E(H))−1. It is shown that f(n,H)/(n2) converges to 1−1/d for n→∞. An analogous result is proved for uniform hypergraphs. If, especially, H is a complete graph Kp, the extremal colouring is, for every n, uniquely determined (up to isomorphisms); it is closely related to the Turán graph (with p−1 colour-classes). The problem of determining f(n,H) is also discussed in more detail in the case when H is a path or a circuit, and in the case of a path an explicit formula is given, holding for n sufficiently large.

Actions (login required)

Edit Item