Математики доказали гипотезу о «графовом сэндвиче», не дававшуюся 20 лет
Mathematicians Build Long-Awaited Graph Sandwich
В 2004 году Kim и Vu предположили, что случайный регулярный граф можно «зажать» между двумя случайными биномиальными графами, что позволило бы переносить свойства с простых графов на сложные. Доказательство нижней половины заняло годы, но верхняя оставалась недостижимой. В 2023 году Montgomery, Behague и Iľkovič разработали рецепт одновременного построения обоих графов ребро за ребром, завершив доказательство. Теперь свойства регулярных графов можно получать бесплатно из биномиальных.
«Гипотеза в каком-то смысле очень естественна. Было немного обидно, что её до сих пор не доказали», — сказал Krivelevich.