Bipartite Ramsey numbers for graphs of small bandwidth (Q1753090): Difference between revisions

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