Premium
On an anti‐Ramsey property of Ramanujan graphs
Author(s) -
Haxell P. E.,
Kohayakawa Y.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240060405
Subject(s) - combinatorics , mathematics , injective function , graph , ramanujan's sum , discrete mathematics
Abstract If G and H are graphs, we write G → H (respectively, G → TH ) if for any proper edge‐coloring γ of G there is a subgraph H' ⊂ G of G isomorphic to H (respectively, isomorphic to a subdivision of H ) such that γ is injective on E ( H' ). Let us write C l for the cycle of length l . Spencer (cf. Erdös 10]) asked whether for any g ⩾ 3 there is a graph G = G g such that (i) G has girth g ( G ) at least g and (ii) G → TC 3 . Recently, Rödl and Tuza [22] answered this question in the affirmative by proving, using nonconstructive methods, a result that implies that, for any t ⩾ 1, there is a graph G = G t of girth t + 2 such that G → C 2 t +2 . In particular, condition (ii) may be strengthened to (iii) G → C for some l = ( G ). For G = G t above = ( G ) = 2 t + 2 = 2 g ( G ) − 2. Here, we show that suitable Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak [18] are explicit examples of graphs G = G g satisfying (i) and (iii) above. For such graphs, = l ( G ) in (iii) may be taken to be roughly equal to (3/2) g ( G ), thus considerably improving the value 2 g ( G ) − 2 given in the result of Rödl and Tuza. It is not known whether there are graphs G of arbitrarily large girth for which (iii) holds with = ( G ) = g ( G ).