Конференции

64-я Всероссийская научная конференция МФТИ

Список разделов ФПМИ - Секция дискретной математики

Секция посвящена проблемам дискретной математики

  • A simpler proof of the Sternfeld theorem

    Штернфельд ввёл комбинаторно-геометрические понятия базисных множеств и массивов в 2n-мерном пространстве. Он доказал следующую теорему: если подмножество 2n-мерного простанства содержит в себе массивы сколь угодно большого размера, тогда оно небазисно. Для доказательства этой теоремы Штернфельд использовал теорему Банаха об обратном операторе. Мы приведём упрощённое комбинаторное доказательство этой теоремы.

  • О технике оценки максимального коэффициента специального полинома.

    Рассмотрена техника оценки максимального коэффициента последовательности A162206 (OEIS), представимой в виде бесконечной таблицы, имеющей треугольную форму. Строка n этой таблицы содержит коэффициенты специального полинома, связанного с группами отражений Dn. Приведено описание методики получения более точных асимптотических оценок с использованием формулы Фаулхабера.

  • Ханойские башни

    Добрый день. Я хотел бы представить мою гипотезу, которая уже совсем близка к доказательству, по нахождению минимального числа перестановок для заданных n - количество стержней и m - количества колец в ханойских башнях со сложностью алгоритма O(1).

  • Betweenness centrality network formation game

    В своей работе я рассмотрел класс теоретико-игрвых моделей с функцией выигрыша - взвешенной betwenness centrality. Рассмотрены модели  в которых агенты образуют связи исключительно самостоятельно, коллективно, а также модели в которых издержки образования связей не одинаковы для разных агентов. Во всех случаях доказан малый диаметр устойчивых сетей, а также ряд вспомогательных утверждений

  • Исследование конечных слов в последовательности первых цифр n!

    Рассмотрим бесконечное слово, n-тый символ которого --- это первая цифра n!. Цель данной работы --- это исследование конечных подслов, встречающихся в нем.



  • Система обслуживания трех очередей со сбалансированной нагрузкой
    Мы рассмотрим систему группового обслуживания трех очередей. В каждый момент времени с некоторой вероятностью в систему поступает заявка, выбирает две случайные очереди и направляется в более короткую из них. Как только в каждой очереди оказывается не менее одной заявки, мгновенно обслуживается по одной заявке из каждой очереди. Установлен критерий эргодичности соответствующей цепи Маркова. Найдено предельное совместное распределение длин очередей.


  • Реконструкции в теории графов. Обзор

    Обзор посвящён вопросу реконструкции в теории графов. Рассмотрены несколько постановок задач о восстановлении графа: по окрестностям вершин и по мультимножеству подграфов. Отдельно отмечены леммы Келли и Кокея и результаты, которые доказаны с их помощью.

  • Quantum generalized Heisenberg algebras

    In this talk, we introduce and study a new class of algebras, which we name quantum generalized Heisenberg algebras (qGHAs, for short), including both the so-called generalized Heisenberg algebras (GHAs, for short) and the generalized down-up algebras , but allowing more parameters of freedom, so as to encompass a wider range of applications and provide a common framework for several previously studied classes of algebras.

  • Hardness of almost embedding simplicial complexes in R^d, II

    Проблема сложности распознования почти вложимости k-комплекса в R^d естественно возникла после обширного исследования сложности распознования вложимости k-комплекса в R^d. Я представлю краткий набросок доказательства обобщения теоремы об NP-трудности распознования почти вложимости k-комплекса в R^d на более широкий класс пар (k, d).

  • Полиномиальность числа слов, порождённых перекладыванием отрезков

    Назовем слово W k-хорошим, если существует перестановка и разбиение единичного отрезка на k частей, каждой из которых отвечает буква алфавита A такие, что в системе, полученной перекладыванием этих k отрезков с помощью перестановки σ слово W наблюдается в качестве эволюции.

    Теорема. Множество k-хороших слов ограничено некоторым полиномом, степень которого зависит от k.

  • Число насыщения в кнезеровском графе с простым циклом.

    В данной работе рассматривается асимптотика поведения числа насыщения кнезеровских графов, содержащих простой цикл.

  • Обобщённое контактное число плоскости для нескольких слоёв

    Рассмотрим расположение нескольких непересекающихся по внутренностям кругов на плоскости, один из которых выделен, где от каждого круга можно дойти до выделенного за $$n$$ шагов, на каждом шаге переходя на касающийся круг. Обозначим через $$f(n)$$ максимальное возможное количество невыделенных кругов в такой конфигурации. Мы доказали выдвинутую Фейеш Тотом и Хеппешем гипотезу о том, что $$f(3)=36$$, а также показали, что $$f(n)\sim\dfrac{2\pi}{\sqrt{3}}n^2$$.

  • Применение спутниковых снимков Sentinel-2 для оценки цены на нефть

    В работе рассмотрен процесс получения и обработки спутниковых снимков миссии Sentinel-2, который образует цельный pipeline («трубопровод данных») от источника информации до результатов моделирования для оценки цены на нефть.

  • Разработка методики на основе графовых алгоритмов по изучению языков программирования

    Данная работа была создана для оптимизации времени при изучении языков программирования. Граф, вершинами которого являются различные разделы какого-либо языка программирования, позволяет студентам систематизировать информацию и упростить изучение.

  • О покрытиях плоских множеств

    Авторами предложены методы улучшения верхних и нижних оценок для различных покрытий множеств на плоскости. Приведены новые оценки для различного количества частей разбиения, а также предложения по обобщению представленных методов. Кроме того, предлагается алгоритм поиска оптимальных разбиений плоских множеств, который позволяет улучшить верхние оценки величины $$d_n$$ в случаях $$10  \le n  \le 17.$$

  • Хроматическое число прямой с несколькими запрещёнными расстояниями и сложность распознавания некоторых мультидистанционных графов

    Мы исследуем сложность распознавания A-дистанционных графов и хроматическое число прямой с множеством запрещённых расстояний A для множества A, являющегося геометрической прогрессией со знаменателем, равным рациональному числу, возведённому в рациональную степень. Для всех таких множеств A найдено хроматическое число прямой с этим множеством запрещённых расстояний и доказана полиномиальность или NP-трудность задачи распознавания нестрого неинъективно A-вложимых в R графов.

  • О покрытиях плоских множеств

    Авторами предложены методы улучшения верхних и нижних оценок для различных покрытий множеств на плоскости. Приведены новые оценки для различного количества частей разбиения, а также предложения по обобщению представленных методов. Кроме того, предлагается алгоритм поиска оптимальных разбиений плоских множеств, который позволяет улучшить верхние оценки величины $$d_n$$ в случаях $$10  \le n  \le 17.$$

  • Стохастические комбинаторные игры

    Данная работа изучает вариации обобщения теории конечных комбинаторных игр на вероятностный случай. Вводите определение эквивалентности стохастических игр. Вводятся и изучаются усечённый вероятностный ним и (полный) вероятностный ним. Доказывается, что ни при каких значениях параметров эти игры неэквивалентны, если они не совпадают тождественно. Делается вывод о большей сложности построения полной теории по сравнению склассическим случаем.