Ф. Петров, семинар "Алгебраическая и другая комбинаторика"
(AAC)


По пятницам в 19:00 (с 6 сентября) в лаборатории Чебышева продолжается семинар по алгебраической и не только комбинаторике.


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

Связные нумерации графов.
Будем отмечать по очереди ребра графа. Сколько способов делать это так, чтобы каждый раз образуемый отмеченными рёбрами граф был связным?

Числа независимости графов типа-Джонсона и их друзья
Рассмотрим граф G(n,k,t), множеством вершин которого являются вектора из {-1,0,1} длины корень из k, а ребра соединяют вершины со скалярным произведением t. Нас интересуют числа независимости таких графов.
Для доказательств нам потребуются инструменты из различных областей комбинаторики: метод усреднения Катоны, изодиаметральное неравенство Клейтмана, теорема Эрдёша — Ловаса о пересекающихся семействах, коды Рида — Соломона и некоторые другие.

Гипотеза чувствительности.
Один из самых неожиданных результатов сезона (Хуанг): чувствительность булевой функции полиномиально эквивалента блочной чувствительности.

Множество без единичных расстояний в шаре единичного радиуса которое больше, чем шар единичного диаметра. Конструкция Fernando Mário de Oliveira Filho, Frank Vallentin.

Независимые множества в гиперграфах и ранги матриц и тензоров. Оценки ранга матрицы через структуру графа ненулевых элементов имеют многочисленные приложения.

Контрпример Ярослава Шитова к гипотезе Хедетниеми.

Асимптотика числа косых таблиц Юнга. По серии работ А. Моралеса, И. Пака и Г. Пановой, основанных на приложениях удивительной формулы крюковы Нарусы.