Связь: username: dmclub server: pdmi.ras.ru
Слово Штурма - бесконечное слово над бинарным алфавитом, такое, что для любого n >= 1 у него ровно n + 1 делителей(подстрок) длины n. Столь простое определение допускает несколько эквивалентных переформулировок, в частности, любая функция aх + b, где a иррационально, однозначно определяет слово Штурма. В докладе будут рассмотрены различные переформулировки определения, а также моноид морфизмов на словах Штурма - оказывается, он порожден тремя морфизмами и совпадает с моноидом эндоморфизмов.
В докладе будут рассмотрены результаты связанные с гипотезой "Sandglass Conjecture", выдвинутой в 1989 году Габором Симонье. Гипотеза говорит о том, что произведение размеров двух систем подмножеств конечного множества A, связанных неким естественным условием не превосходит 2^|A|. Эта гипотеза, несмотря на простоту и естественность формулировки, до сих пор не была доказана. На докладе будет предъявлено доказательство наилучшей на данный момент оценки числа в гипотезе(~2,32^n), использующее понятие информационной энтропии. Также будет рассмотрено одно обобщение исходной гипотезы на случай произвольных решёток и доказано для частного случая.
Понимание доклада не требует дополнительных знаний. Все используемые определения будут даны на докладе.
Доклад по книге Р.Стенли "Перечислительная комбинаторика".
Говоря нестрого, "метод решета" в перечислительной комбинаторике есть метод определения мощности множества S, который начинает с большего множества и каким-либо способом вычитает или аннулирует нежелательные элементы.
Метод будет показан на примерах: формула включений-исключений, доски Ферре и др.
Доклад по статье N.Alon. "Packings with large minimum kissing numbers"
В докладе будет описана такая конструкция конечного числа непересекающихся по внутренним точкам шаров в R^n, что каждый шар касается не менее, чем 2^{\sqrt{n}} других шаров.
Граф G(V,E) называется с-расширителем, если для любого множества вершин S (|S|<|V|/2) число ребер между S и V\S не менее с|S|. В докладе будут рассказано о простейших свойствах графов-расширителей, а также будет приведена довольно простая конструкция графов-расширителей константной степени.
Расширители имеют неожиданные применения в разных областях математики и информатики.
Рассмотрим граф G, количество ребер в котором делится на k. Пусть R(G, k) - такое минимальное число r, что при любой раскраске ребер полного графа из r вершин в k цветов в нем содержится подграф, изоморфный G, сумма чисел на ребрах которого делится на k. Таким образом, R(G, k) - обобщение классических чисел Рамсея. В докладе будет рассказано о получении некоторых оценок для этих чисел.
Доклад по статье N. Alon, D.J. Kreitman. A Purely Combinatorial Proof of the Hadwiger Debrunner (p; q) Conjecture
Предположим, что семейство выпуклых множеств обладает свойством, что из каждого подмножества из p множеств любые q из них имеют общую точку. Будет ли отсюда следовать, что существует множество из f(p,q) точек такое что оно пересекает их всех? В докладе будет дан ответ на этот вопрос.
Классическое применение жадного алгоритма: задача о выборе заявок. Когда применимы жадные алгоритмы? Применение в кодах Хаффмена, задаче о расписании. Теоретические основы жадных алгоритмов: матройды, жадные алгоритмы для взвешенного матройда.
В докладе будет изложен метод доказательства теорем дискретной математики с помощью математической логики, придуманный Ю.В. Матиясевичем. В качестве примеров будут доказаны: Konig's theorem, L.M.Vitaver's theorem, и нечто похожее на The Four Colour Theorem(для случая гамильтоновых графов)
Рассмотрим следующую задачу: У Алисы и Боба есть по n-битному вектору x и y, причём каждому неизвестен вектор другого. Коммуникационной сложностью функции F(x,y) называется минимальное число бит, которое необходимо передать друг другу, чтобы вычислить значение функции. В докладе будут рассказано о методах получения нижних оценок для этой величины.
Будем рассматривать полные ориентированные графы с n вершинами -- турниры с n участниками. Изучим вопрос: сколько нужно знать исходов игр между конкретными двумя участниками, чтобы полностью восстановить картину общего турнира между всеми n участниками?
В 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 для произвольного графа через его геометрические параметры, и поставлен ряд открытых вопросов в данной области теории графов.
Теорема Ш.-В. -- утверждение о том, что однородная полиномиальная система над конечным полем, имеющая сумму степеней меньше, чем число неизвестных имеет нетривиальное решение. Это утверждение позволяет строить неконструктивные доказательства существования в задачах теории графов. Например: докажите, что в графе без петель со степенью каждой вершины не более чем 5 и средней степенью больше 4 -- есть подграф, степень каждой вершины которого равна 3. И т. д.
Второе применение -- конечные группы. В докладе будет сформулирована и доказана Теорема Эрдеша-Гинзбурга-Зива в максимальной общности, а также, если успеем, другие оценки.
Этот доклад имеет прямое отношение к докладу Ф.В.Петрова, хотя те, кто на нем не были -- ничего не потеряют.
Покрывающий код (двоичный) радиуса R - такой код, что все остальные элементы пространства {0,1}^n находятся на расстоянии не более R от одного из кодовых слов.
Задача состоит в построении "маленьких" кодов с "большим" радиусом. В докладе будет рассказано о нижних границах размера кода и основных методах построения. Также будут упомянуты применения покрывающих кодов: SAT и задача о гномах, людоеде и шапках.
Мы расскажем о недавнем гениально простом изобретении замечательного израильского математика Ноги Алона - комбинаторной теореме о нулях, приведшей к настоящему прорыву в комбинтарике (главным образом в аддитивной арифметике). Будет рассмотрено несколько примеров, включающих долго стоявшие проблемы, удивительно легко решаемые с помощью CN.
В 1955 году М. Кнезер сформулировал гипотезу: невозможно разбить все n-элементные подмножества 2n+k-элементного множества на k+1 класс так, чтобы в каждом классе множества попарно пересекались. В 1978 году L. Lovasz доказал эту гипотезу, сумев привлечь к ней методы алгебраической топологии. Это доказательство дало начало новой дисциплине - топологической комбинаторике.
Доказательство гипотезы Кнезера, которое будет рассказано в докладе, принадлежит Джошуа Грину (2002 год). Это доказательство (как и предыдущие) опирается на топологическую теорему - теорему Улама-Борсука, поэтому мы поговорим об этой теореме и о других её применениях в комбинаторике.
В связи с тем, что на семинаре будут не только русскоговорящие студенты, возможно доклад будет сделан по-английски.
В докладе планируется рассказать три интересных доказательства трех задач по алгебраической теории графов.
Первая задача. Все мы хорошо знаем, что латинский квадрат --- это квадрат n на n, каждая клетка которого покрашена в один из n цветов так, чтобы в каждой строке и столбце все клетки бы имели разный цвет. Такой квадрат легко можем сами нарисовать. Теперь усложним себе задачу. Пусть уже в квадрате со стороной n не противоречивым образом раскрашены не более n-1 клеточки, тогда квадрат можно докрасить до латинского.
Вторая задача. Пусть теперь мы можем покрасить каждую клетку квадрата n на n в n каких-то различных цветов, но не обязательно от 1 до n. Тогда можно так раскрасить квадрат, чтобы в каждой строке и в каждом столбце не было одноцветных клеток.
Третья задача. Есть несколько человек, причем для любых двух из них найдется ровно один их общий знакомый. Тогда есть человек, который знакомый со всеми.
Докладчик советует прийти всем, кого интересует теория графов и алгебраические идеи применяемые в ней.
Вероятностный метод основан на очень простом соображении: вместо того, чтобы доказывать, что некоторый объект существует, достаточно доказать, что вероятность его существования больше нуля. Вероятностный метод помогает доказывать (и порою - очень красиво доказывать) существование "причудливых" дискретных объектов без конструктивного построения.
В докладе будут изложены основы вероятностного метода. Будут показаны применения к широкому классу комбинаторных задач. Кроме уже сказанного, метод позволяет как находить оценки в задачах на экстремум, так и доказывать их. Материал доступен студентам младших курсов.