On bipartite graphs with linear Ramsey numbers (Q5955195)
From MaRDI portal
scientific article; zbMATH DE number 1703944
Language | Label | Description | Also known as |
---|---|---|---|
English | On bipartite graphs with linear Ramsey numbers |
scientific article; zbMATH DE number 1703944 |
Statements
On bipartite graphs with linear Ramsey numbers (English)
0 references
13 February 2002
0 references
The upper bound \(8(8\Delta)^{\Delta}n\) is proved for the Ramsey number of \(n\)-vertex bipartite graphs with largest degree \(\Delta\). This gives a \(2^{cn\log n}\) bound for the \(n\)-cube. In the other direction, probabilistic methods give the existence of a constant \(c>1\) such that for \(\Delta\geq 1\), \(n\geq \Delta+1\), unless \(\Delta=1\) and \(n=2,3,5\), there exists a bipartite \(n\)-vertex graph with maximum degree \(\Delta\) and Ramsey number at least \(c^{\Delta}n\).
0 references
Ramsey numbers
0 references
Ramsey graphs
0 references
probabilistic methods
0 references