КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер проекта 22-21-00202

НазваниеРаскраски и структуры в гиперграфах

Руководитель Тараненко Анна Александровна, Кандидат физико-математических наук

Организация финансирования, регион федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук , Новосибирская обл

Конкурс №64 - Конкурс 2021 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-114 - Дискретная математика и математическая кибернетика

Ключевые слова гиперграф, случайный граф, модель Эрдёша-Реньи, совершенная раскраска, правильная раскраска, хроматическое число, индекс Винера, многомерная матрица, перманент, совершенная структура, паросочетание, произведение тензоров

Код ГРНТИ27.45.00

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Основная цель проекта — разработка и совершенствование методов поиска, перечисления и описания раскрасок и других структур в гиперграфах и связанных с ними объектах, которые бы удовлетворяли определенным локальным ограничениям. Для продвижений по этой проблеме будут решаться следующие задачи. 1) Получить алгебраические условия и ограничения на существование совершенных раскрасок и структур в гиперграфах, аналогичных известным результатам для графов. Провести исследование операции накрытия для гиперграфов и их связи с трансверсалями и паросочетаниями. Построить совершенные раскраски и структуры в ряде конструкций гиперграфов, основанных на произведении. Вопрос о совершенных раскрасках в гиперграфах, которые являются естественным обобщением графов, является новым и пока практически не затронут ни в одной из существующих работ. В исследованиях по этому вопросу предполагается адаптация уже существующих алгебраических методов в теории графов к гиперграфам, а также разработка новых. 2) Исследовать многомерные (0,1)-матрицы, экстремальные для наличия полидиагонали, и многодольные однородные гиперграфы, экстремальные для наличия дробного совершенного паросочетания. Проблема характеризации сбалансированных однородных многодольных гиперграфов, экстремальных для наличия дробного совершенного паросочетания, по-видимому, ранее подробно не рассматривалась и была впервые поставлена в одной из работ руководителя проекта. Для описания и изучения этих объектов мы предполагаем использовать новый подход, основанный на представлении их в качестве (0,1)-функций в q-ичном гиперкубе. 3) Задача поиска неотрицательных диагоналей в неотрицательной многомерной матрице. Впервые исследовать изменения перманента многомерных матриц для различных операций произведения. 4) Оценить математическое ожидание количества одноцветных гиперребер в случайных раскрасках неоднородных простых гиперграфов. По аналогии с известными результатами для величины минимального числа гиперребер в классе однородных гиперграфов с хроматическим числом больше двух, наложенные условия на гиперграфы должны позволить заметно улучшить существующие оценки. 5) Впервые вычислить индекса Винера в случайных графах. Исследовать его распределение в классической модели Эрдёша-Реньи G(n,p), получить оценки на его значение для широкого диапазона параметра p. Рассматриваемые проблемы в первую очередь имеют теоретическую значимость, но объекты, которые являются предметом исследования, имеют множество практических приложений в системах передачи, хранения и обработки информации, в теории кодирования и в криптографических системах. Кроме того, индекс Винера часто применяется на практике для характеризации структурных свойств графа различных химических соединений.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---