Premium
Cube Ramsey numbers are polynomial
Author(s) -
Lingsheng Shi
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.1021
Subject(s) - ramsey's theorem , combinatorics , bipartite graph , mathematics , graph , cube (algebra) , order (exchange) , integer (computer science) , complete bipartite graph , upper and lower bounds , degree (music) , discrete mathematics , physics , computer science , acoustics , programming language , mathematical analysis , finance , economics
Let R ( G ) be the least integer p such that for all bicolorings of the edges of complete graph K p , at least one of the monochromatic subgraphs contains a copy of G . We show that for any positive constant c and bipartite graph G =( U , V ; E ) of order n where the maximum degree of vertices in U is at most $c\,{\rm log}\,n,\,R(G) < n^{1+(c+\sqrt{c^2+4c})/2+o(1)}.$ In particular, this shows that the Ramsey number of the n ‐cube Q n satisfies $R(Q_n)<2^{(3+\sqrt{5}n/2+o(n)}$ which improves the bound 2 cn log n due to Graham, Rödl, and Ruciński. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 99–101, 2001