Loading...
Please wait, while we are loading the content...
Similar Documents
Path Ramsey Number for Random Graphs
| Content Provider | Scilit |
|---|---|
| Author | Letzter, Shoham |
| Copyright Year | 2015 |
| Description | Answering a question raised by Dudek and Prałat, we show that if pn → ∞, w.h.p., whenever G = G(n, p) is 2-edge-coloured there is a monochromatic path of length (2/3 + o(1))n. This result is optimal in the sense that 2/3 cannot be replaced by a larger constant.As part of the proof we obtain the following result. Given a graph G on n vertices with at least $(1-\varepsilon)\binom{n}{2}$ edges, whenever G is 2-edge-coloured, there is a monochromatic path of length at least $(2/3 - 110\sqrt{\varepsilon})n$ . This is an extension of the classical result by Gerencsér and Gyárfás which says that whenever $K_{n}$ is 2-coloured there is a monochromatic path of length at least 2n/3. |
| Related Links | http://arxiv.org/pdf/1405.6670 http://arxiv.org/abs/1405.6670 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/90F860EB214AA823AEED8A4315BADC00/S0963548315000279a.pdf/div-class-title-path-ramsey-number-for-random-graphs-div.pdf |
| Ending Page | 622 |
| Page Count | 11 |
| Starting Page | 612 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548315000279 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 4 |
| Volume Number | 25 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2016-07-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Mathematical Physics Primary 05d10 Secondary 05c80 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
