| Автор | Rhee, Wansoo T. |
| Дата выпуска | 1990 |
| dc.description | Consider a function f defined on the set of graphs on a fixed set of n vertices. Assume that f satisfies the following “continuity” condition: (<sup>*</sup>) |f(G) - f(G′)| ≦ 1 whenever G and G′ differ by at most one edge. (An example of such a function f is the maximum matching of the graph G) Then we prove that in either of the classical models and G <sub>n,p</sub> of random graphsf is very concentrated around its expectation. (The concentration bounds we obtain are of optimal order.). |
| Формат | application.pdf |
| Издатель | Akademic-Verlag |
| Копирайт | Copyright Taylor and Francis Group, LLC |
| Тема | Martingale inequality |
| Тема | random graphs |
| Тема | maximum matching size |
| Тема | Primary: 60 C 05 |
| Тема | Secondary: 60 G 42 |
| Название | A concentration inequality for maximum matching size in random graphs |
| Тип | research-article |
| DOI | 10.1080/02331939008843608 |
| Electronic ISSN | 1029-4945 |
| Print ISSN | 0233-1934 |
| Журнал | Optimization |
| Том | 21 |
| Первая страница | 797 |
| Последняя страница | 803 |
| Аффилиация | Rhee, Wansoo T.; Faculty of Management Science, The Ohio State University |
| Выпуск | 5 |
| Библиографическая ссылка | Maurey, B. 1979. Espaees de BANACH; Constructions de Suites Symetriques. Comptes Rendus, Acad. Sci. Paris, 288: 678–681. |
| Библиографическая ссылка | Hoeffding, W. 1963. Probability Inequalities for Sums of Bounded Random Variables. J. Am. Stat. Assoc, 58: 13–30. |
| Библиографическая ссылка | Rhee, W. and Talagband, M. 1987. Martingale Inequalities and NP-Complete Problems. Math, of Oper. Res, 12(1): 177–181. |
| Библиографическая ссылка | Rhee, W. and Talagband, M. 1989. Martingale Inequalities, Interpolation and NP-Complete Problems. Math, of Oper. Res, 14(1): 91–96. |
| Библиографическая ссылка | Stout, W.F. 1974. Almost Sure Convergence, Academic Press. |
