Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-29T10:16:18.291Z Has data issue: false hasContentIssue false

Book Ramsey Numbers and Quasi-Randomness

Published online by Cambridge University Press:  11 October 2005

V. NIKIFOROV
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee, TN 38152, USA (e-mail: [email protected], [email protected], [email protected])
C. C. ROUSSEAU
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee, TN 38152, USA (e-mail: [email protected], [email protected], [email protected])
R. H. SCHELP
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee, TN 38152, USA (e-mail: [email protected], [email protected], [email protected])

Abstract

A set of n triangles sharing a common edge is called a book with n pages and is denoted by $B_{n}$. It is known that the Ramsey number $r ( B_{n} ) $ satisfies $r ( B_{n} ) = ( 4+o ( 1 ) ) n.$ We show that every red–blue edge colouring of $K_{ \lfloor ( 4-\varepsilon ) n \rfloor }$ with no monochromatic $B_{n}$ exhibits quasi-random properties when $\varepsilon$ tends to 0. This implies that there is a constant $c>0$ such that for every red–blue edge colouring of $K_{r ( B_{n} ) }$ there is a monochromatic $B_{n}$ whose vertices span at least $ \lfloor cn^{2} \rfloor $ edges of the same colour as the book.

As an application we find the Ramsey number for a class of graphs.

Type
Paper
Copyright
2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)