Раскраски пространств с запрещенными одноцветными конфигурациями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Самиров Дмитрий Вячеславович

РАСКРАСКИ ПРОСТРАНСТВ С ЗАПРЕЩЕННЫМИ ОДНОЦВЕТНЫМИ КОНФИГУРАЦИЯМИ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации па соискание ученой степени кандидата физико-математических наук

г I ОКТ 2015

Москва - 2015

005563608

005563608

Работа выполнена на кафедре дискретной математики Московского физико-технического института (государственного университета)

Научный руководитель: Официальные оппоненты:

Ведущая организация:

Райгородский Андрей Михайлович, доктор физико-математических наук

Кабатянский Григорий Анатольевич,

доктор физико-математических паук, Институт Проблем Передачи Информации имени A.A. Харкевича РАН, Лаборатория ,\s4, главный научный сотрудник

Карпов Дмитрий Валерьевич,

кандидат физико-математических наук, Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН, лаборатория математической логики, старший научный сотрудник

Хабаровское отделение Института прикладной математики Дальневосточного отделения РАН

Защита состоится 19 ноября 2015 г. в 12 часов 40 минут на заседании диссертационного совета Д 212.156.05 на базе Московского физико-технического института (государственного университета) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета) и на сайте университета http://www.mipt.ru/.

Автореферат разослан " |'2." ■ОИ-'С-Эс^ШЗ. 2015 г.

Ученый секретарь диссертационного совета

Федько Ольга Сергеевна

Общая характеристика работы

Актуальность темы.

Диссертация посвящена решению ряда классических задач, которые находятся на стыке комбинаторной геометрии, экстремальной теории графов н гиперграфов, экстремальной комбинаторики, теории Раысея и теории кодирования.

С точки зрения комбинаторной геометрии центральными являются задачи, в которых изучаются комбинаторные свойства геометрических объектов и их взаимных расположений. Именно поэтому комбинаторная геометрия берет свое начало в XIX веке, когда Вороной, Коркин, Золотарев, Мипковский и др.1 начинают изучение разбиений евклидова пространства па многогранники2. В начале XX века появятся работы Хелли3,4, в которых речь пойдет об отыскании условий для существования трапсверсалей в семействах тел в евклидовых пространствах. Наконец, в 1933 году Борсук опубликует классическую работу5, из которой впоследствии вырастет современный топологический метод в комбинаторике6 н которая в то же время ляжет в основу целого ряда активно изучаемых проблем в комбинаторной геометрии. Разумеется, первая из этих проблем носит имя самого Бор-сука, и состоит она в отыскании минимального числа частей /(п) меньшего диаметра, на которые может быть разбито произвольное множество диаметра 1 в n-мерном евклидовом пространстве. Этой проблеме посвящено гигантское количество исследований, и ее до сих пор нельзя считать полностью решенной7,8,9.

Вторая по времени возникновения, по не менее важная по сути проблема восходит к Хадвигеру10. Однако в современном своем виде она была сформулирована в 1950 году Нелсопом, который задался вопросом о том, чему равно минимальное количество цветов, в которые можно так раскрасить все точки евклидовой плоскости, чтобы между точками одного цвета не было расстояния I11. Вопрос сродни проблеме Борсука, ведь, если у Борсука речь идет о разбиении множеств диаметра 1 на части меньшего диаметра (т.е. на части, которые заведомо пе содержат пар точек на расстоянии 1), то у Нелсона похожая задача ставится для всего пространства (плоскости). Соответственно, описанное выше минимальное число цветов принято обозначать х№2) и называть хроматическим числом плоскости. Естественно, так же определяется и хроматическое число пространства х(К"). Проблема отыскания этого числа носит сейчас название проблемы Нелсона-Хадвигера или даже Нелсона-Эрдеша-Хадвигсра. В последнем случае отмечается колоссальная роль, которую сыграл замечательный венгерский комбинаторщик Эрдеш в популяризации задачи. Сейчас работам по проблеме Нелсона-Хадвигера посвящено едва ли не больше публика-

^.Ф. Вороной, Собрание сочинений Т. 1 - 3, Киев, 1952 - 1953.

2Дж. Конвей, Н. Слоэн, Упаковки шаров, решетки и группы, Москва, "Мир", 1990.

3JI. Данцер, Б. Грюнбаум, В. Кли, Теорема Хелли, Москва, "Мир", 1968.

4Г. Хадвигер, Г. Дебруннер, Комбинаторная геометрия плоскости, Москва, "Наука", 1965.

5К. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundamenta Math., 20 (1933), 177 - 190.

6J. Matousck, Using the Borsuk - Ulam theorem, Universitext, Springer, Berlin, 2003.

7A.M. Raigorodskii, Cliques and cycles in distance graphs and graphs of diameters, "Discrcte Geometry and Algebraic Combinatorics", AMS. Contemporary Mathematics, 625 (2014), 93 - 109.

8A.M. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometrie Graph Theory, J. Fach ed., Springer, 2013, 429 - 460.

9A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи ыатем. наук, 56 (2001), вып. 1, 107- 146.

10Н. Hadwiger, Ein Überdeckungssatz für den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144.

11 Л. Soifcr, The Mathematical Coloring Book, Springer, 2009.

ций, чем работам по проблеме Борсука12,13,14.

Тот факт, что проблема Нелсона-Хадвигера столь популярна, связан, конечно, отнюдь не только с харизмой Эрдеша и других замечательных популяризаторов. Дело, скорее, в том, что, как мы уже говорили, проблема оказалась на стыке целого ряда важнейших дисциплин, которые активно развивались и продолжают развиваться благодаря собственной исключительной значимости. Ниже мы поговорим об этих дисциплинах.

Прежде всего проблема Нелсона-Хадвигера тесно связана с классической проблематикой раскраски графов15. Однако здесь идет речь не о раскрасках карт, а о раскрасках вершин так называемых дистанционных графов. В самом деле, пусть G = (V, Е) — граф, у которого вершины — точки в M", а ребра — пары точек, отстоящих друг от друга на расстояние 1. Пусть, далее, хроматическое число графа — это, как обычно, наименьшее количество цветов, в которые можно так раскрасить все вершины, чтобы концы любого ребра имели разные цвета. Обозначим ,\(G) хроматическое число графа G. Попятно, что максимальное значение хроматического числа дистанционного графа — это и есть хроматическое число пространства. Более того, хроматическое число пространства, будучи, как несложно показать, всегда конечным16, достигается на конечном дистанционном графе ввиду старой теоремы Эрдеша-де Брцйна17.

Родство задачи Нелсона-Хадвигера с теорией гиперграфов чуть менее очевидно. Дело, однако же, в том, что наиболее распространенный класс дистанционных графов, с помощью которых удается хорошо оценивать снизу хроматические числа пространств, состоит из графов, вершины которых суть вершины булева куба, т.е. (ОД)-векторы. В свою очередь, расстояния между векторами задаются их скалярными произведениями, которые для (0,1)-векторов однозначно соответствуют количествам общих единиц у этих векторов. Иными словами, вершины таких дистанционных графов разумно интерпретировать как ребра гиперграфа, у которого п вершин (если речь шла про К"), а ребра имеют такие мощности, сколько единиц было в соответствующих вершинах исходного дистанционного графа. В этом случае задача об отыскании максимально большого числа вершин дистанционного графа, которые можно покрасить в один цвет (такое число называется числом независимости графа, а множества одноцветных вершин — это независимые множества), — это задача о наибольшем числе ребер в гиперграфе с одним запрещенным пересечением. А это задача классическая18,19.

Из предыдущего абзаца очевидно, что проблема Нелсона-Хадвигера имеет тесную связь и с теорией кодирования. А именно, в терминах последней число независимости дистанционного графа с вершинами в точках целочисленной решетки с координатами, имеющими право принадлежать заданному наперед множеству целых чисел, — это код с одним запрещенным расстоянием20'21.

12А.М. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, J. Pach ed., Springer, 2013, 429 - 460.

13P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

14P.K. Agarwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995.

15Ф. Харари, Теория графов, Москва, "Мир", 1973.

16А.М. Райгородский, Хроматические числа, Второе издание, МЦНМО, Москва, Россия, 2014.

17N.G. de Bruijn, Р. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), N5, 371 - 373.

18P. Frankl, V. Rödl, Forbidden intersections, Trans. Amer. Math. Soc., 300 (1987), N1, 259 - 286.

19P. Prank!, R. Wilson, Intersection theorems with geometric consequences , Combinatorica, 1 (1981), 357 -368.

20Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, М.: Радио и связь, 1979.

21L. Bassalygo, G. Cohen, G. Zcmor, Codes with forbidden distances, Discrete Mathematics, 213 (2000), 3 -

Наконец, теория Рамеея, если говорить совсем общо, — это наука о том, что при любом разбиении на несколько частей достаточно большого множества объектов найдется элемент разбиения, содержащий некоторую наперед заданную структуру22: полного хаоса в очень больших системах не бывает. Так, классические рамсеевскне теоремы утверждают, что для любого к при любой раскраске ребер достаточно большого полного графа в два цвета найдется полный подграф на к вершинах, у которого все ребра одного цвета23, что при любой раскраске множества натуральных чисел в конечное число цветов найдутся сколь угодно длинные одноцветные арифметические прогрессии24, и т.д. В этом ключе утверждение о том, что хроматическое число пространства стремится к бесконечности (очевидно, что х(К") ^ п+1, ведь вершины правильного «-мерного симплекса необходимо красить в разные цвета), также является рамсеевским, ведь его можно переформулировать следующим образом: для любого г найдется такое п0, что при всех п > щ и при любой раскраске точек R" в г цветов найдутся две точки на расстоянии 1, покрашенные в один и тот же цвет.

Из приведешюй выше интерпретации возникла целая наука, которая называется евклидова теория Рамсея. Задача этой науки охарактеризовать множества точек, обладающих тем же свойством, что и пары точек на расстоянии 1: множество S рамсеевское, если для любого г найдется такое п0, что при всех п > щ и при любой раскраске точек R" в г цветов найдется множество точек одного и того же цвета, конгруэнтное множеству S. Одна из самых трудных проблем здесь — доказательство или опровержение гипотезы о том, что S рамсеевское тогда и только тогда, когда S лежит на сфере. Гипотеза доказана только для симплексов (в частности, для треугольников)25'26, для декартовых произведений рамсеевских множеств и еще для буквально нескольких специальных классов. Но даже для тех классов, для которых гипотеза доказана, очень трудны оценки соответствующих хроматических чисел.

Настоящая работа посвящена получению оценок указанного типа в случае раскрасок пространств с запрещенными одноцветными равнобедренными треугольниками.

Цель работы и основные задачи. Основными задачами работы являются нижние оценки хроматических чисел евклидовых пространств, в определении которых точкам одного цвета запрещено быть вершинами равнобедренных треугольников с данными длинами равных сторон и данным диапазоном значений длин оснований. Цель работы состоит в развитии линейно-алгебраической и вероятностной техники в теории кодирования и теории графов.

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

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая значимость полученных результатов. Диссер-

11.

22R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory, John Wily and Sons, NY, Second Edition, 1990.

23F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser. 2, 30 (1930), 264 - 286.

24А.Я. Хинчин, Три жемчуэ^сипы теории чисел, Москва, "Эдиторнал УРСС, 2004.

25Р. Frankl, V. Rödl, All triangles are Ramsey, Transactions of the Amer. Math. Soc., 297 (1986), N2, 777 -779.

26P. Frankl, V. Rödl, A partition property of simplices in Euclidean space, J. Ainer. Math. Soc., 3 (1990), N1, 1 - 7.

тацпя носит теоретический характер. Полученные в ней результаты дают новую информацию о рамсеевскнх свойствах евклидова пространства. Эти результаты важны для теории графов и гнперграфов, теории Рамсея, теории кодирования и для комбинаторной геометрии. Они могут быть полезны специалистам Московского физико-технического института, Института проблем передачи информации им. А.А. Харкевича РАН, механико-математического факультета МГУ им. М.В. Ломоносова, факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, Хабаровского отделения Института прикладной математики ДВО РАН и др. Они могут быть использованы при чтении обязательных и специальных курсов, связанных с дискретной математикой и теоретической информатикой.

Основные положения диссертации, выносимые на защиту.

1. Получены новые экспоненциальные нижние оценки величины

ХоДК"), равной наименьшему числу цветов, в которые можно так покрасить все точки R", чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон 1 и длиной основания в пределах от а до Ь. Развита линейно-алгебраическая и вероятностная техника.

2. Получены новые экспоненциальные нижние оценки величины

X„j,(R")> равной максимуму среди всех величин Ха,ь,с(К"), каждая из которых определяется как наименьшее число цветов, в которые можно так покрасить все точки М", чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон с и длиной основания в пределах от а до Ь.

3. Результаты предыдущего пункта перенесены па случай, когда максимизируются величины Xa,b,ci,...,ci(K"), каждая из которых определяется как наименьшее число цветов, в которые можно так покрасить все точки R", чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон Ci и длиной основания в пределах от а до Ь.

Степень достоверности и апробация результатов. Материалы диссертации опубликованы в 8 работах, из которых 5 в изданиях, рекомендованных ВАК РФ [1, 3, 4, 7, 8]. Список этих работ приведен в конце автореферата. Также результаты докладывались и получили одобрение специалистов па международной конференции "4th Polish Combinatorial Conference" в Бедлево (Польша, 2012 г.), па ежегодных научных конференциях МФТИ (Долгопрудный-Москва, 2012 г., 2013 г.), а также на научных семинарах'под руководством профессора A.M. Райгородского в МФТИ (кафедра дискретной математики) и в МГУ им. М.В. Ломоносова (кафедра математической статистики и случайных процессов) (2012 - 2015 г. г.). Достоверность полученных результатов подтверждается применением современных методов экстремальной комбинаторики и теории кодирования.

Структура и объем диссертации Диссертация состоит из введения, трех глав, заключения, списка условных обозначений и списка литературы. Общий объем диссертации составляет 62 страницы. Список литературы содержит 70 наименований.

Основное содержание работы

Во введении к диссертации дается общий обзор наиболее актуальных направлений дискретной математики, связанных с задачами, которые рассматриваются в работе. Также во введении приводятся основные определения. Так, определяется величина Ха,ь(Кп) (при 0 < а < 1 < ö < %/2), равная минимальному количеству цветов, в которые можно так покрасить все точки евклидова пространства, чтобы никакие три точки одного цвета не образовывали равнобедренный треугольник с длинами боковых сторон 1 и длиной основания в пределах от а до Ь. Разумеется, если в данном определении единицу заменить каким-нибудь числом с, то получится некоторое новое хроматическое число Ха,б,с(К"). Соответственно, вводится величина

Х„ь(М") = шахХа,Ь,с(К")-

с

Наконец, определяется хроматическое число ХаАсь...,с,(®") как минимальное количество цветов, в которые можно так покрасить все точки евклидова пространства, чтобы никакие три точки одного цвета не образовывали равнобедренный треугольник с длинами боковых сторон Ci и длиной основания в пределах от а до b, i = 1,..., I. Рассматривается величина

ХоЛ,(М") = шах XaAcl,...,c,(Kn).

Ci,...,C I

Поясняется, что ввиду классических результатов Лармана-Роджсрса27 Хаы(®") 5= (3+ о(1))1", а стало быть, мотивирована задача об отыскании ?сижних оценок такого хроматического числа, чему в итоге и посвящена диссертация.

В первой главе диссертации разрабатывается вероятностно-алгебраический подход к получению нижних оценок величин Ха,ь(1Кп) при разных а и Ь. Используются нетривиальные модификации полиномиальной техники28 в сочетании с техникой "малых вариаций", применяемой в вероятностной комбинаторике и теории кодирования29. Также используются результаты Алсведе-Хачатряна о наибольшем числе ребер гиперграфа, у которого попарные пересечения ребер не меньше заданной величины30,31. В итоге оказывается, что при многих значениях a, b нижние оценки величины Хо,ь(5К") имеют экспоненциальный по п рост, где основание экспоненты зависит от а, Ь и вычисляется с помощью следующей теоремы.

Теорема 1. Пусть 0<а<1<Ь< \/2, 0 < к < 0 < 7 < к,

а = к- Ь2(к - у), ß = к - а2(к - 7), г = —.

1 + 2(а — к)

При а > О их £ [ß — к + or + г, а + г] положим

Ci = (а + 2г)"+2г • (а + г)~а~г ■ г~г ■ (1 - а - 2г)1-п"2г • (к - а - r)r+Q"K-

"D.G.

Larman, С.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

28A.M. Рай городским, Линейно-алгебраический метод в комбинаторике, МЦНМО, Москва, Россия, 2015, второе издание.

29Н. Алон, Дж. Сиснсср, Вероятностный метод, Москва: Бином. Лаборатория знаний, 2007.

30R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory A, 76 (1996), 121 - 138.

31R. Ahlswede, V.M. Blinovsky, Lectures on advances in combinatorics, Springer, 2008.

С2(:г) = (а + г)а+г ■ х~х • (а + г - х)2(1-а"г) ■ гг ■ (х - а)0"1, С3(х) = (к - а - г)к-"-г • (/3 - х)1"" .(к + х-а-Р- г)

•(1 - к - г)1_"~г . (1 + а + уЗ_х_ гк)142"-1"0^,

А = тахС^ж) • С3(:г:).

Тогда

А • (к - 7)Т-« • (1 + 7 - к)«-т-1 +

Численные результаты, получаемые из теоремы 1, приведены в таблице в разделе 1.1. Доказательству теоремы 1 посвящен раздел 1.2.

В главе 2 строится новый вероятностно-алгебраический подход к задаче отыскания нижних оценок числа ,\а,б(1К"). За счет этого удается установить экспоненциалыюсть роста при многих а, Ь, для которых подход из главы 1 не давал нужного результата. Основными в главе 2 являются следующие две теоремы.

Теорема 2. Пусть 0<а<\<Ь< л/2, 0 < к < 0 < 7 < к,

а = к — Ъ2(к — 7), ¡3 = к — а2(к — у), г =

а(к — а)

1 + 2(а — к)

При а>0ихЕ{/3 — к + а +г, а +г] положим

С] = (а + 2г)°+2г • (а + г)~°~Г ■ г~Т ■ (1 - а - 2г)1-°"2'' -(к-а- г)г+а~к-

•(1 — к — г)г+к-1, С2(х) = (а + г)а+г • аТ* • (а + г - х)2^~а~г> ■ гг ■ (х - а)а~х, С3(х) = (к - а - Гу-а~г • (0 - ху-*3 .(к + х-а-Р- .

•(1 - к - г)1-"-* .(1 + а + р-х-2к)х+2к-1-"-в, А = тахС2(:г) • С3(х).

X

Положим также

5 =

к — 7

7 — а

, Р = '

к — 7

'

Допустим, р> ¡3 — у. Тогда Ха,ь{ I

Теорема 3. Пусть 0<а<1<Ь< \/2, 0 < к < А, к - р < у < к, а = к - Ь2{к — 7), /3 = к — а2(к — 7).

Положилг

6 =

к — 7

Зафиксируй г € {1,..., <5} и расслютрим

к - 7 , а'(к - а')

—:—, а =тах{а,7 — р), г =

1 +2(а' - к)'

При у & [0,к], х€ [у — к + + г, а' + г] положим

С1 = (а' + 2г)с,Ч2г • (о' + г)-°'-г ■ г-г ■ (1 - а' - 27-)1""'-2'' ■ (к - а' - г)г+а'~

■(1-к-гГ-1,

С2(х) = (а' + г)"'+г ■ х-1 ■ (а' + г - х)2^"'-^ ■ тТ ■ (х - а')"'-1,

Сз(1, у) = (к - а - г)к~а'~г ■ {у - ху-у ■ (к + х-а'-у-

•(1 - к - г)1~к~Г • (1 + а' + у-х- 2к)х+2к-1~а'-\

А = тахСг(х) • Сз(х,у). х,У

Тогда

В разделе 2.2 произведено численное сопоставление результатов теорем 1-3, а в разделах 2.3, 2.4 доказаны обе новые теоремы.

В главе 3 изучены величины Для них также получены экспоненциальные

нижние оценки. А именно, справедлива следующая теорема.

Теорема 4. Пусть 0 < а < Ь < I € N. Возьмель любые числа к, а, удовлетворяющие ограничениям 0 < к < 5, 0 < а < к. Положим

/3 = к-—{к-а), 6 =

(/ + !)(«:-а)

р -а а(к — о)

к — о

. Р =

5 '

1 + 2(а — к)

При хе [0 — к + а + г, а + г] положим

Сх = (а + 2г)а+2г • (а + г)"°"г • г~Т ■ (1 - о - 2г)1~а-2г ■ (к - а - г)г+а~к

•(1 -к-гГ"1, С2(х) = (а + г)а+г • х~х ■ (а + г - х)2(х~а~г) • гг • (х - а)"-х, С3(х) = (к - а - г)к-°-г ■ (/? - х)1-" -(к + х-а-0- г)2^+г-к~х »■ •(1 - к - г)1-~-г. (1 + а + /з-2; - гк)^2"-1-0-", А = тахС2(х) • Сз(х).

X

Тогда

ЫшП>.{С^-{1х-ру-р + о{ 1))".

В серии таблиц приведены численные результаты при разных a, b, I. Для доказательства также использована новая модификация линейно-алгебраического и вероятностного методов в комбинаторике.

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

Соискатель считает своим приятным долгом поблагодарить д.ф.-м.н., проф. A.M. Рай-городского за постоянный интерес и внимание к его работе.

Работы автора по теме диссертации

1. Самиров Д.В., Райгородский A.M. Хроматические числа прост ранете с запрещенными одноцветными треугольниками // Матем. заметки. — 2013. — Т. 93, вып. 1. - С. 134 - 143.

2. Самиров Д.В., Райгородский A.M. Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками // Итоги пауки и техники, Современная математика и ее приложения. — 2013. — Т. 125. — С. 252 - 268.

3. Самиров Д.В., Райгородский A.M. Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками // Доклады РАН. - 2014. - Т. 456, вып. 3. - С. 280 - 283.

4. Самиров Д.В., Райгородский A.M. Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников // Труды МФТИ. - 2015. - Т. 7, вып. 2 (26). - С. 39 - 50.

5. Самиров Д.В., Райгородский A.M. Хроматическое число пространства с запрещенными равнобедренными треугольниками // Труды 55-й научной конференции МФТИ. /Моск. физ. — техн. ни-т. —М. — Долгопрудный, 2012. — С. 29 - 30.

6. Салшров Д.В., Райгородский A.M. Новые нижние оценки хроматических чисел пространств с запрещенными равнобедренными треугольниками // Труды 56-й научной конференции МФТИ. /Моск. физ. — техн. ин-т. —М. — Долгопрудный, 2013. — С. 29.

7. Звонарев А.Е., Райгородский A.M., Самиров Д.В., Харламова A.A. Улучшение теоремы Франкла-Рчдля о числе ребер гиперграфа с запретами на пересечения. // Доклады РАН. - 2014. - Т. 457, вып. 2. - С. 144 - 146.

8. Звонарев А.Е., Райгородский A.M., Самиров Д.В., Харламова A.A. О хроматическом числе пространства с запрещенным равносторонним треугольником. // Матем. сборник. - 2014. - Т. 205, вып. 9. - С. 97- 120.

Личный вклад соискателя. В работах [1-6] Д.В. Самировым были самостоятельно сформулированы и доказаны основные результаты, A.M. Райгородский помогал в редактировании текста. В работах [7, 8] Д.В. Самиров помогал в подсчете итоговых оценок.

Самиров Дмитрий Вячеславович

РАСКРАСКИ ПРОСТРАНСТВ С ЗАПРЕЩЕННЫМИ ОДНОЦВЕТНЫМИ КОНФИГУРАЦИЯМИ

АВТОРЕФЕРАТ

Подписано в печать 05.10.2015. Формат 60 х 84 'Дб- Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 396. Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет" Отдел оперативной полиграфии "Физтех-полиграф" 141700, Московская обл., г. Долгопрудный, Институтский пер., 9