Семинар по дискретной математике

Целью семинара является знакомство участников (и организаторов) с красивыми и важными результатами и интересными методами в современных (и не очень) областях комбинаторики, теории графов, математической логики и теоретической информатики (все то, что называют дискретной математикой).

Связь: username: dmclub server: pdmi.ras.ru

14.12.07 ПОМИ к. 106 16-00. Е. Шавердова. Слова Штурма.

Слово Штурма - бесконечное слово над бинарным алфавитом, такое, что для любого n >= 1 у него ровно n + 1 делителей(подстрок) длины n. Столь простое определение допускает несколько эквивалентных переформулировок, в частности, любая функция aх + b, где a иррационально, однозначно определяет слово Штурма. В докладе будут рассмотрены различные переформулировки определения, а также моноид морфизмов на словах Штурма - оказывается, он порожден тремя морфизмами и совпадает с моноидом эндоморфизмов.

07.12.07 ПОМИ к. 106 16-00. А. Банкевич. Гипотеза о песочных часах (Sandglass Conjecture).

В докладе будут рассмотрены результаты связанные с гипотезой "Sandglass Conjecture", выдвинутой в 1989 году Габором Симонье. Гипотеза говорит о том, что произведение размеров двух систем подмножеств конечного множества A, связанных неким естественным условием не превосходит 2^|A|. Эта гипотеза, несмотря на простоту и естественность формулировки, до сих пор не была доказана. На докладе будет предъявлено доказательство наилучшей на данный момент оценки числа в гипотезе(~2,32^n), использующее понятие информационной энтропии. Также будет рассмотрено одно обобщение исходной гипотезы на случай произвольных решёток и доказано для частного случая.

Понимание доклада не требует дополнительных знаний. Все используемые определения будут даны на докладе.

30.11.07 ПОМИ к. 106 16-00. Е. Деменков. Методы решета.

Доклад по книге Р.Стенли "Перечислительная комбинаторика".

Говоря нестрого, "метод решета" в перечислительной комбинаторике есть метод определения мощности множества S, который начинает с большего множества и каким-либо способом вычитает или аннулирует нежелательные элементы.

Метод будет показан на примерах: формула включений-исключений, доски Ферре и др.

23.11.07 ПОМИ к. 106 16-00. А. Звонарева. Целующиеся шары.

Доклад по статье N.Alon. "Packings with large minimum kissing numbers"

В докладе будет описана такая конструкция конечного числа непересекающихся по внутренним точкам шаров в R^n, что каждый шар касается не менее, чем 2^{\sqrt{n}} других шаров.

16.11.07 ПОМИ к. 106 16-00. Н. Калинин. Недостаточно широко известные свойства таблиц Юнга.

Алгоритм RSK ставит в соответствие каждой перестановке из n элементов пару таблиц Юнга. Мы займёмся им, а также другими свойствами таблиц Юнга - объекту пристального внимания теории представлений и математической физики. (Тем не менее, за пределы комбинаторики выходить мы, увы, не будем.)

09.11.07 ПОМИ к. 106 16-00. Д. Ицыксон. Графы-расширители (expanders).

Доклад по статье N. Alon, O. Schwartz, A. Shapira. An elementary construction of constant-degree expanders.

Граф G(V,E) называется с-расширителем, если для любого множества вершин S (|S|<|V|/2) число ребер между S и V\S не менее с|S|. В докладе будут рассказано о простейших свойствах графов-расширителей, а также будет приведена довольно простая конструкция графов-расширителей константной степени.

Расширители имеют неожиданные применения в разных областях математики и информатики.

02.11.07 ПОМИ к. 106 16-00. Е. Лысенко. Взвешивания.

В докладе будет рассказано, за сколько взвешиваний можно определить, все ли монеты одинаковы, если известно, что различных весов не более K.

26.10.07 ПОМИ к. 106 16-00. А. Зыкова. Обобщенные числа Рамсея.

Доклад по статье N.Alon. On three zero-sum Ramsey-type problems.

Рассмотрим граф G, количество ребер в котором делится на k. Пусть R(G, k) - такое минимальное число r, что при любой раскраске ребер полного графа из r вершин в k цветов в нем содержится подграф, изоморфный G, сумма чисел на ребрах которого делится на k. Таким образом, R(G, k) - обобщение классических чисел Рамсея. В докладе будет рассказано о получении некоторых оценок для этих чисел.

19.10.07 ПОМИ к. 106 16-00. И. Манаев. Проблема Дебруннера-Хадвигера.

Доклад по статье N. Alon, D.J. Kreitman. A Purely Combinatorial Proof of the Hadwiger Debrunner (p; q) Conjecture

Предположим, что семейство выпуклых множеств обладает свойством, что из каждого подмножества из p множеств любые q из них имеют общую точку. Будет ли отсюда следовать, что существует множество из f(p,q) точек такое что оно пересекает их всех? В докладе будет дан ответ на этот вопрос.

12.10.07 ПОМИ к. 106 16-00. К. Шмаков. Жадные алгоритмы и матройды.

Классическое применение жадного алгоритма: задача о выборе заявок. Когда применимы жадные алгоритмы? Применение в кодах Хаффмена, задаче о расписании. Теоретические основы жадных алгоритмов: матройды, жадные алгоритмы для взвешенного матройда.

05.10.07 ПОМИ к. 106 16-00. Е. Деменков. Метаматематические доказательства в дискретной математике.

В докладе будет изложен метод доказательства теорем дискретной математики с помощью математической логики, придуманный Ю.В. Матиясевичем. В качестве примеров будут доказаны: Konig's theorem, L.M.Vitaver's theorem, и нечто похожее на The Four Colour Theorem(для случая гамильтоновых графов)

07.05.07 ПОМИ к. 311 19-20. А. Зыкова. Коммуникационная сложность.

Рассмотрим следующую задачу: У Алисы и Боба есть по n-битному вектору x и y, причём каждому неизвестен вектор другого. Коммуникационной сложностью функции F(x,y) называется минимальное число бит, которое необходимо передать друг другу, чтобы вычислить значение функции. В докладе будут рассказано о методах получения нижних оценок для этой величины.

30.04.07 ПОМИ к. 311 19-20. Е. Лысенко. Восстановление турниров.

Будем рассматривать полные ориентированные графы с n вершинами -- турниры с n участниками. Изучим вопрос: сколько нужно знать исходов игр между конкретными двумя участниками, чтобы полностью восстановить картину общего турнира между всеми n участниками?

23.04.07 ПОМИ к. 311 19-20. Д. Ширяев. Об одном применении графов в теории информации.

В 1956 году Клод Шеннон, один из создателей математической теории информации, поставил следующий интересный вопрос: "Suppose we want to transmit messages across a channel (where some symbols may be distorted) to a receiver. What is the maximum rate of transmission such that the receiver may recover the original message without errors?"

В докладе будет представлена интерпретация поставленной Шенноном задачи на языке теории графов (вершинами графов будут символы, а ребрами будут соединяться пары символов, которые могут путаться при передаче по информационному каналу).

Будет дано определение такого параметра графа, как zero-error capacity, играющее ключевую роль при решении основной задачи, и оно будет вычислено для циклического графа на 5 вершинах (красивый результат, полученный Лэсло Ловасом сравнительно недавно). Будут также даны оценки на zero-error capacity для произвольного графа через его геометрические параметры, и поставлен ряд открытых вопросов в данной области теории графов.

16.04.07 ПОМИ 18-00. М. Иванов. Теорема Шевалле-Варнинга.

Теорема Шевалле-Варнинга -- это официальное название доклада. Правильнее было бы назвать его алгебраические методы в теории графов и теории групп.

Теорема Ш.-В. -- утверждение о том, что однородная полиномиальная система над конечным полем, имеющая сумму степеней меньше, чем число неизвестных имеет нетривиальное решение. Это утверждение позволяет строить неконструктивные доказательства существования в задачах теории графов. Например: докажите, что в графе без петель со степенью каждой вершины не более чем 5 и средней степенью больше 4 -- есть подграф, степень каждой вершины которого равна 3. И т. д.

Второе применение -- конечные группы. В докладе будет сформулирована и доказана Теорема Эрдеша-Гинзбурга-Зива в максимальной общности, а также, если успеем, другие оценки.

Этот доклад имеет прямое отношение к докладу Ф.В.Петрова, хотя те, кто на нем не были -- ничего не потеряют.

09.04.07 ПОМИ к. 311 19-20. В. Мальков. Покрывающие коды.

Покрывающий код (двоичный) радиуса R - такой код, что все остальные элементы пространства {0,1}^n находятся на расстоянии не более R от одного из кодовых слов.

Задача состоит в построении "маленьких" кодов с "большим" радиусом. В докладе будет рассказано о нижних границах размера кода и основных методах построения. Также будут упомянуты применения покрывающих кодов: SAT и задача о гномах, людоеде и шапках.

02.04.07 ПОМИ к. 311 19-20. Ф.В. Петров. Комбинаторная Nullstellensatz.

Мы расскажем о недавнем гениально простом изобретении замечательного израильского математика Ноги Алона - комбинаторной теореме о нулях, приведшей к настоящему прорыву в комбинтарике (главным образом в аддитивной арифметике). Будет рассмотрено несколько примеров, включающих долго стоявшие проблемы, удивительно легко решаемые с помощью CN.

26.03.07 ПОМИ к. 311 19-20. О. Сергеева. Топологические методы в комбинаторике: применения теоремы Улама-Борсука.

В 1955 году М. Кнезер сформулировал гипотезу: невозможно разбить все n-элементные подмножества 2n+k-элементного множества на k+1 класс так, чтобы в каждом классе множества попарно пересекались. В 1978 году L. Lovasz доказал эту гипотезу, сумев привлечь к ней методы алгебраической топологии. Это доказательство дало начало новой дисциплине - топологической комбинаторике.

Доказательство гипотезы Кнезера, которое будет рассказано в докладе, принадлежит Джошуа Грину (2002 год). Это доказательство (как и предыдущие) опирается на топологическую теорему - теорему Улама-Борсука, поэтому мы поговорим об этой теореме и о других её применениях в комбинаторике.

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

19.03.07 ПОМИ к. 203 19-20. Н. Гравин. Задача Диница о латинских квадратах. Задача о друзьях и политиканах.

В докладе планируется рассказать три интересных доказательства трех задач по алгебраической теории графов.

Первая задача. Все мы хорошо знаем, что латинский квадрат --- это квадрат n на n, каждая клетка которого покрашена в один из n цветов так, чтобы в каждой строке и столбце все клетки бы имели разный цвет. Такой квадрат легко можем сами нарисовать. Теперь усложним себе задачу. Пусть уже в квадрате со стороной n не противоречивым образом раскрашены не более n-1 клеточки, тогда квадрат можно докрасить до латинского.

Вторая задача. Пусть теперь мы можем покрасить каждую клетку квадрата n на n в n каких-то различных цветов, но не обязательно от 1 до n. Тогда можно так раскрасить квадрат, чтобы в каждой строке и в каждом столбце не было одноцветных клеток.

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

Докладчик советует прийти всем, кого интересует теория графов и алгебраические идеи применяемые в ней.

12.03.07 ПОМИ к. 306 19-00. М.А. Антипов. Вероятностный метод

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

В докладе будут изложены основы вероятностного метода. Будут показаны применения к широкому классу комбинаторных задач. Кроме уже сказанного, метод позволяет как находить оценки в задачах на экстремум, так и доказывать их. Материал доступен студентам младших курсов.