Читать онлайн «Системы общих представителей в комбинаторике и их приложения в геометрии»

Летняя школа «Современная математика» Дубна, июль 2008 А. М. Райгородский Системы общих представителей в комбинаторике и их приложения в геометрии Москва Издательство МЦНМО 2009 УДК 519. 1 ББК 22. 15 Р18 Райгородский А. М. Р18 Системы общих представителей в комбинаторике и их прило- жения в геометрии. — М. : МЦНМО, 2009. — 136 с. ISBN 978-5-94057-524-5 Настоящая книга посвящена различным аспектам задачи о системах общих представителей в комбинаторике. Рассказывается о многочисленных приложе- ниях в комбинаторной геометрии, геометрии чисел, математической статистике и др. Книга написана по лекциям, которые ее автор читал в 2007 году на школе «Современная математика» в Дубне. Поэтому материал в ней изложен так, что- бы бо́льшая его часть оказалась доступной первокурсникам. Однако материала много, и в конечном счете в книге возникает весьма нетривиальная техника, в том числе вероятностная. Книга будет интересна всем, кто интересуется современной комбинаторикой и ее приложениями. УДК 519. 1 © Райгородский А. М. , 2009. ISBN 978-5-94057-524-5 © МЦНМО, 2009. Предисловие Посвящается моей жене Ире В настоящей книге мы расскажем об одном из красивейших разделов современной комбинаторики. Речь пойдет о так называемых системах общих представителей для совокупностей подмножеств конечного мно- жества. Грубо говоря, система представителей — это любое множество, которое содержит хотя бы по одному «представителю» (элементу) из каждого множества, принадлежащего данной совокупности. Отыскание таких систем (в особенности минимальных) — это исключительно важная проблема дискретного анализа, которая имеет массу приложений в самых разнообразных областях знания. Так, имеются целые классы известных проблем в геометрии, решение которых напрямую зависит от того, как на данном этапе развития науки обстоят дела с построением оптимальных систем представителей для тех или иных совокупностей множеств. Среди этих проблем и классическая задача К. Борсука о разбиении множеств на части меньшего диаметра, и знаменитая задача Нелсона—Эрдёша— Хадвигера о раскрасках пространств, и задача Грюнбаума о покрытии множеств шарами. Имеются также красивые приложения систем общих представителей в геометрии чисел, которая является ярким и активно развивающимся разделом теории чисел. Имеется, наконец, и глубокая связь с понятием размерности Вапника—Червоненкиса — одним из цен- тральных понятий в теории сложности и в математической статистике. В этой книге мы подробно расскажем как о чисто комбинаторных свойствах систем общих представителей, так и об упомянутых выше при- ложениях этих объектов в геометрии, статистике и пр. Начнем мы с самых азов, но затем разовьем достаточно нетривиальную технику. Впрочем, для понимания материала будет абсолютно достаточным знание пред- метов, которые преподаются, скажем, на первых двух курсах механико- математического факультета МГУ им.