Статьи по комбинаторике

Разделите комбинаторику по задачам

• extremal graph theory — сколько рёбер или подграфов может быть при заданном запрете.
• graph coloring — раскраски вершин и рёбер.
• Ramsey theory — неизбежные упорядоченные структуры в больших объектах.
• enumerative combinatorics — подсчёт объектов, производящие функции, тождества.

Готовые запросы для arXiv

Все эти направления входят в math.CO. Для алгоритмов на графах полезен также cs.DS, а для случайных графов — math.PR. Само слово graph встречается и в машинном обучении, поэтому рубрика особенно помогает.

В «Сложном запросе» первый пример ищет раскраски в комбинаторике, второй — случайные графы в вероятностях или комбинаторике.

(cat:math.CO AND all:"graph coloring")
((cat:math.CO OR cat:math.PR) AND all:"random graph")

Настройте уведомления по одному направлению

В боте откройте «Добавить тему» → arXiv → «Раздел arXiv» и отправьте math.CO. Бот ответит «Добавлено». Более узкий вариант: выберите «Ключевую фразу» и отправьте Ramsey theory или graph coloring.

В «Последних работах» выберите эту подписку и просмотрите заголовки. Если вместо вашей задачи идут статьи о моделях графовых нейросетей, используйте сложное условие с cat:math.CO.

Как понять, относится ли новая оценка к вашей задаче

Посмотрите, какой граф рассматривается: ориентированный или неориентированный, простой или мультиграф, регулярный или произвольный. Затем найдите, какой параметр обозначен через n и от чего зависят скрытые константы. Это позволяет быстро отобрать полезные статьи, не читая каждое доказательство целиком.

Английские термины для поиска

graph coloring

раскраска графа

extremal graph theory

экстремальная теория графов

generating function

производящая функция

Частые вопросы