| Автор | Zdeborová, Lenka |
| Автор | Boettcher, Stefan |
| Дата выпуска | 2010-02-01 |
| dc.description | The asymptotic properties of random regular graphs are objects of extensive study in mathematics and physics. In this paper we argue, using the theory of spin glasses in physics, that in random regular graphs the maximum cut size asymptotically equals the number of edges in the graph minus the minimum bisection size. Maximum cut and minimal bisection are two famous NP-complete problems with no known general relation between them; hence our conjecture is a surprising property for random regular graphs. We further support the conjecture with numerical simulations. A rigorous proof of this relation is an obvious challenge. |
| Формат | application.pdf |
| Издатель | Institute of Physics Publishing |
| Копирайт | IOP Publishing Ltd |
| Название | A conjecture on the maximum cut and bisection width in random regular graphs |
| Тип | paper |
| DOI | 10.1088/1742-5468/2010/02/P02020 |
| Electronic ISSN | 1742-5468 |
| Журнал | Journal of Statistical Mechanics: Theory and Experiment |
| Том | 2010 |
| Первая страница | P02020 |
| Последняя страница | 12 |
| Аффилиация | Zdeborová, Lenka; Theoretical Division and Center for Nonlinear Studies, Los Alamos National Laboratory, NM 87545, USA |
| Аффилиация | Boettcher, Stefan; Physics Department, Emory University, Atlanta, GA 30322, USA |
| Выпуск | 02 |
