Two remarks on the Burr-Erdos conjecture

Details Two remarks on the Burr-Erdos conjecture Two remarks on the Burr-Erdos conjecture

2008-03-12

arxiv.org/abs/0803.1860v1

Mathematics

Combinatorics

18 pages

Scientific paper

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erd\H{o}s in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H) \leq c_dn for every d-degenerate graph H on n vertices. We show that for such graphs r(H) \leq 2^{c_d\sqrt{\log n}}n, improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.

Affiliated with

Also associated with

No associations

Rating

Two remarks on the Burr-Erdos conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two remarks on the Burr-Erdos conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two remarks on the Burr-Erdos conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-69340