On an anti‐Ramsey property of Ramanujan graphs

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 ).