Bipartite Ramsey numbers for graphs of small bandwidth
type: Item
instance of: scholarly article
title: Bipartite Ramsey numbers for graphs of small bandwidth
zbMATH Open document ID: 1391.05181
author: Lili Shen
author: Qizhong Lin
author: Qinghai Liu
published in: The Electronic Journal of Combinatorics
publication date: 2018-05-25T00:00:00Z
full work available at URL: v25i2p16
review text: Summary: A graph \(H=(W,E_H)\) is said to have \textit{bandwidth} at most \(b\) if there exists a labeling of \(W\) as \(w_1,w_2,\dots,w_n\) such that \(|i-j|\leq b\) for every edge \(w_iw_j\in E_H\), and a \textit{bipartite balanced \((\beta,\Delta)\)-graph} \(H\) is a bipartite graph with bandwidth at most \(\beta |W|\) and maximum degree at most \(\Delta\), and furthermore it has a proper 2-coloring \(\chi :W\rightarrow[2]\) such that \(||\chi^{-1}(1)|-|\chi^{-1}(2)||\leq\beta|\chi^{-1}(2)|\). We prove that for any fixed \(0<\gamma<1\) and integer \(\Delta\geq1\), there exist a constant \(\beta=\beta(\gamma,\Delta)>0\) and a natural number \(n_0\) such that for every balanced \((\beta,\Delta)\)-graph \(H\) on \(n\geq n_0\) vertices the bipartite Ramsey number \(br(H,H)\) is at most \((1+\gamma)n\). In particular, \(br(C_{2n},C_{2n})=(2+o(1))n\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 6873167
zbMATH Keywords: bipartite Ramsey number
zbMATH Keywords: balanced \((\beta,\Delta)\)-graph
zbMATH Keywords: regularity lemma
MaRDI profile type: Publication
cites work: Q4100119
cites work: Embedding into Bipartite Graphs
cites work: \(K_{2,2}\)-\(K_{1,n}\) and \(K_{2,n}\)-\(K_{2,n}\) bipartite Ramsey numbers
cites work: Asymptotic bounds for bipartite Ramsey numbers
cites work: A new upper bound for the bipartite Ramsey problem
cites work: Recent developments in graph Ramsey theory
cites work: Path-path Ramsey type numbers for the complete bipartite graph
cites work: Q3903002
cites work: An extremal problem for paths in bipartite graphs
cites work: Q3839723
cites work: A bipartite Ramsey problem and the Zarankiewicz numbers
cites work: Q4878666
cites work: Ramsey functions involving \(K_{m,n}\) with \(n\) large
cites work: A Folkman Linear Family
cites work: Bipartite Ramsey numbers involving large \(K_{n,n}\)
cites work: Ramsey numbers for bipartite graphs with small bandwidth
cites work: On Certain Sets of Integers
cites work: On Certain Sets of Integers (II)
cites work: Ramsey's theorem - a new lower bound
cites work: On sets of integers containing k elements in arithmetic progression
cites work: Q4200109
cites work: On finite Ramsey numbers
cites work: The bipartite Ramsey numbers
Recommended article: Ramsey numbers for bipartite graphs with small bandwidth
Recommended article: Q5419960
Recommended article: Q3428645
Recommended article: Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth
Recommended article: Ramsey theory and bandwidth of graphs
Recommended article: Ramsey numbers of large books and bipartite graphs with small bandwidth
Recommended article: Bounds on Ramsey numbers of certain complete bipartite graphs
Recommended article: Asymptotic Size Ramsey Results for Bipartite Graphs
Recommended article: Barycentric Ramsey numbers for small graphs
Recommended article: On bipartite graphs with linear Ramsey numbers
description: scientific article; zbMATH DE number 6873167