Two remarks on the Burr-Erdos conjecture
| dc.creator | Fox, Jacob | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2008-03-12 | |
| dc.date.accessioned | 2026-07-07T09:26:33Z | |
| dc.date.available | 2026-07-07T09:26:33Z | |
| dc.description | 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ő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. | |
| dc.description | 18 pages | |
| dc.identifier | https://arxiv.org/abs/0803.1860 | |
| dc.identifier | http://arxiv.org/abs/0803.1860 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/156788 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C55; 05C80; 05D10 | |
| dc.title | Two remarks on the Burr-Erdos conjecture | |
| dc.type | text |