Can I read On an anti‐Ramsey property of Ramanujan graphs on EtoBox?

On an anti‐Ramsey property of Ramanujan graphs by P. E. Haxell; Y. Kohayakawa is a Mathematics article available to read on EtoBox.

What is On an anti‐Ramsey property of Ramanujan graphs about?

## 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^l^__ for some __l__ = l(__G__). For __G__ = __G~t~__ above l = l(__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 = __l__(__G__) in (iii) may be taken to be roughly equ

Who reads On an anti‐Ramsey property of Ramanujan graphs?

Author

P. E. Haxell; Y. Kohayakawa

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 1042-9832)

Published

1995

Language

EN

Field

Mathematics (Physical Sciences)