Ramsey numbers of large books and bipartite graphs with small bandwidth

Abstract The book B n ( k ) is the graph consisting of n copies of K k + 1 , all sharing a common K k . A graph H = ( W , E H ) is said to have bandwidth at most b if there exists a labeling of W as w 1 , w 2 , … , w n such that | i − j | ≤ b for every edge w i w j ∈ E H . We say H = ( W , E H ) is a bipartite balanced ( β , Δ ) -graph if it is a bipartite graph with bandwidth at most β | W | and maximum degree at most Δ, and furthermore it has a proper 2-coloring χ : W → [ 2 ] such that | | χ − 1 ( 1 ) | − | χ − 1 ( 2 ) | | ≤ β | χ − 1 ( 2 ) | . In this paper, we prove that for fixed integer k ≥ 2 and every bipartite balanced ( β , Δ ) -graph H on n vertices, the Ramsey number r ( B n ( k ) , H ) ≤ ( k + 1 + o ( 1 ) ) n . As a corollary, we have that for fixed k ≥ 2 and t ≥ 2 , r ( B t n ( k ) , θ n , t ) = ( k + 1 + o ( 1 ) ) t n , where θ n , t is the graph consisting of t internally disjoint paths of length n all sharing the same endpoints.