Какой вопрос решают
Нужно разбить людей, вершины или объекты на допустимые пары так, чтобы каждый участвовал ровно один раз. Существование одного решения не показывает, много ли альтернатив и насколько хрупок выбор.
Заявлена полностью полиномиальная рандомизированная схема относительного приближения числа совершенных паросочетаний в произвольном простом неориентированном графе, а не только в двудольном.
Почему выбрано: Подсчёт и генерация — близкие к программным продуктам задачи; эта работа также появляется как вход в расширении группы 131.
До и после
Классический результат Jerrum–Sinclair–Vigoda относится к перманенту и двудольным совершенным паросочетаниям. Подсчёт всех паросочетаний всех размеров тоже не эквивалентен подсчёту только совершенных. Введение новой работы не просто переносит старую цепь на общий граф: используются расширенные состояния.
Это сопоставление по введению рукописи. Независимый исчерпывающий обзор приоритета не выполнен.
Точное утверждение и условия
113-01, теорема 1.1, PDF с. 2: для явного конечного простого графа, рациональных 0<ε<1 и 0<δ<1/2 алгоритм выдаёт рациональное Ẑ с вероятностью ≥1−δ в интервале [(1−ε)Z,(1+ε)Z]. При Z=0 вывод всегда 0. Битовая сложность ограничена полиномом от длины входа, ε⁻¹ и log δ⁻¹ на каждом запуске, включая неудачные.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Перекодировать граф и обеспечить контроль состояний с дефектами относительно бездефектных.
Построить цепь на произведении состояний с соседними энергетическими уровнями и оценить её смешивание.
Телескопическим произведением отношений получить счётчик и реализовать весь процесс ограниченной битовой арифметикой.
Что известно о проверке
Scope notes заявляют охват FPRAS и отдельного энтропийного неравенства. Геометрические утверждения о размерности граней нельзя автоматически включать в этот охват. Локальный формальный запуск отсутствует.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Небольшой счётчик разнообразия допустимых пар и стенд проверки оценок на графах, где полный ответ можно вычислить независимо. Новый FPRAS стоит подключать только после отдельной реализации и верификации.
Ограничения переноса
Общие пары — не произвольная задача назначения с тройками, весами и бизнес-ограничениями. Скрытый полином может быть непригоден; относительная ошибка при очень редких решениях требует аккуратного контроля. Не обещается готовый быстрый равномерный генератор для всех расширений модели.
Планы проверки: Счётчик разнообразия допустимых пар.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
113-01 · A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General Graphs
Реальный охват: Просмотрены PDF с. 1–3: Постановка, теорема, историческое сопоставление и оглавление доказательства. Полный объём PDF: 45 с.
math_sources/math_research_07_of_08/preprints/A-Fully-Polynomial-Randomized-Approximation-Scheme-for-Perfect-Matchings-in-General-Graphs-September-23-2026/main.pdfSHA-256: 1510b15725ee7e92a6c543484c6c02ce7f26347a32c1a11cd66c5890b94c6de1Каталог: context/CONTENTS.md, строка 2775. Путь и хеш относятся к загруженной версии.
113-02 · Entropy and Face Dimension of the Perfect-Matching Polytope
Реальный охват: Только каталог; полный текст автоматически доступен для поиска у отобранных компаньонов, но здесь не прочитан. Полный объём PDF: 45 с.
math_sources/math_research_07_of_08/preprints/Entropy-and-Face-Dimension-of-the-Perfect-Matching-Polytope-September-23-2026/main.pdfSHA-256: c0b726a089502900b6b0c6b26b3d024cc55c440ce5d4abc71584b2c9ffe2fae4Каталог: context/CONTENTS.md, строка 2784. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 2768. Структурированные заметки · Журнал внешней сверки.