Name
Abstract | ||
|---|---|---|
Given a large graph H, does the binomial random graph G(n, p) contain a copy of H as an induced subgraph with high probability? This classical question has been studied extensively for various graphs H, going back to the study of the independence number of G(n, p) by Erdos and Bollobas and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if C/n <= p <= 0.99 for some large constant C, then G(n, p) contains an induced matching of order approximately 2 log(q)(np), where q = 1/1 - p. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1137/20M1330609 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
random graphs, induced matchings, Talagrand's inequality, Paley-Zygmund inequality | Journal | 35 |
Issue | ISSN | Citations |
1 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oliver Cooley | 1 | 39 | 9.15 |
| Draganić Nemanja | 2 | 0 | 0.68 |
| Mihyun Kang | 3 | 163 | 29.18 |
| Sudakov Benny | 4 | 0 | 0.34 |