Эта страница переведена с помощью средств машинного перевода. Смотреть оригинал

Хроматические числа симплициальных многообразий.

Авторы
ИзданиеarXiv.org.
Год издания2015

 Более высокие хроматические числа симплициальных комплексов естественно обобщают хроматическое число графа. Тем не менее, мало известно о более высоких хроматических числах для конкретных симплициальных комплексов. 2-хроматическое число любой неподвижной поверхности конечно. Однако асимптотически 2-хроматическое число поверхностей становится сколь угодно большим с растущим родом (как мы увидим в тройных системах Штейнера). Показано, что ориентируемые поверхности рода не менее 20 и неориентируемых поверхностей рода не менее 26 имеют 2-хроматическое число не менее 4. С помощью проективных тройных систем Штейнера строится явная триангуляция неориентируемой поверхности рода 2542 и граничного вектораf=(127,8001,5334), Который имеет 2-хроматическое число 5 или 6. Мы также приводим ориентируемые примеры с 2-хроматическими числами 5 и 6. Для 3-мерных многообразий построение итеративной кривой момента может быть использовано для создания триангуляции со сколь угодно большим 2-хроматическим числом [6, 18], но с огромными размерами. Через топологическую версию геометрической конструкции [18] мы показываем первую конкретную триангуляцию 3-мерной сферыS3, С вектором лицаf=(167,1579,2824,1412), Который имеет 2-хроматическое число 5.

 22 страницы, 11 рисунков, теорема 2.18 добавлено

Ссылка на публикацию
Лутз Ф. Х., Мøллер Д. М.  Хроматические числа симплициальных многообразий. - : , 2015. // arXiv.org, 2015.
Библиография
1.A. Альтшулер, Своеобразная триангуляция 3-сферы, Proc. Амер. Математика. Soc. 54 (1976), 449-452.
2.К. Аппель и У. Хакен, Каждая плоская карта четыре цвета, Бык. Амер. Математика. Soc. 82 (1976), 711-712.
3.B. Бенедетти и Ф. ЧАС. Лутц, Библиотека триангуляций, 2013-2015, http: // страница.Математика.Ту-берлин.De / lutz / stellar / library_of_triangulations /. ~
4., Узлы в складных и нескладных шарах, Электрон. J. Расческа. 20, No. 3, Исследовательская работа P31, 29 p. (2013).
5., Случайная дискретная теория Морса и новая библиотека триангуляций, Exp. Математика. 23 (2014), 66--94.
6.Р. ЧАС. Бинг, Геометрическая топология 3-многообразий, Коллоквиум Публикации, вып. 40, American Mathematical Society, Providence, RI, 1983.
7.A. Bj? Orner и F. ЧАС. Лютц, Симплициальные многообразия, бистеллярные флипы и триангуляция 16 вершин трехмерной сферы гомологии Пуанкаре, Exp. Математика. 9 (2000), 275-289.
8.Р. С. Бозе, О построении сбалансированных неполных конструкций блоков, Ann. Eugenics 9 (1939), 353-399.
9.A. Bruen, L. Хаддад и Д. Wehlau, Шапки и раскраски тройных систем Штейнера, Des. Коды Cryptogr. 13 (1998), 51-55.
10.М. Де Брандес, К. T. Фелпс и В. R? Odl, раскраски тройных систем Штайнера, SIAM J. Алгебраические дискретные методы 3 (1982), 241-249.
11.Г. A. Дирак, Теоремы о цветовой окраске, Кан. J. Математика. 4 (1952), 480-490.
12.D. М. Донован, М. J. Grannell, T. S. Griggs, J. Г. Лефевр и Т. Маккорт, Самообъединения циклических и проективных квазигрупп Штейнера, J. Комбинация. Des. 19 (2011), 16-27.
13.J. Fug`ere, L. Хаддад и Д. Велау, 5-хроматическая тройная система Штейнера, J. Комбинация. Des. 2 (1994), 287-299.
14.М. Р. Garey, D. S. Джонсон и Л. Стокмайер, Некоторые упрощенные NP-полные задачи графа, Теорема. Вычисл. Sci. 1 (1976), 237-267.
15.М. J. Grannell, T. S. Григгс и Дж. Поверхностные вложения тройных систем Штейнера, J. Комбинация. Des. 6 (1998), 325-336.
16.Максимальные вложения рода тройных систем Штейнера, Eur. J. Расческа. 26 (2005), 401-416.
17.L. Хаддад, О хроматических числах тройных систем Штейнера, J. Комбинация. Des. 7 (1999), 1- 10.
18.С. Г. Heise, K. Панагиотоу, О. Пикурко и А. Тараз, Окраски d-вложенных k-равномерных гиперграфов, дискретные вычисления. Geom. 52 (2014), 663-679.
19.T. Р. Дженсен и Б. Toft, Проблемы раскраски графов, Серия Wiley-Interscience в дискретной математике и оптимизации, John Wiley & Sons, Нью-Йорк, 1995.
20.Р. М. Карп, Приводимость комбинаторных задач, Сложность вычислительных вычислений (Р. E. Миллер и Дж. W. Тэтчер., Eds.), Пленум, Нью-Йорк, Нью-Йорк, 1972, стр. 85--103.
21.М. Кривелевич и Б. Судаков, Хроматические числа случайных гиперграфов, Random Struct. Алгоритмы 12 (1998), 381-403.
22.A. K? Undgen и R. Рамамурти, Раскраска граней на графах на поверхностях, J. Комбинация. Теория Сер. B 85 (2002), 307-337.
23.Р. Лидл и Г. L. Mullen, Нерешенные проблемы: Когда полином над конечным полем переставляют элементы поля?, Amer. Математика. Monthly 95 (1988), no. 3, 243-246.
24.Г. J. Лавгроув, Группы автоморфизмов тройных систем Штейнера, полученные по построению Бозе, Дж. Алгебраическая комбинация. 18 (2003), 159-170.
25.F. ЧАС. Лутц, Страница коллектора, 1999--2015, http: // страница.Математика.Ту-берлин.De / lutz / звездный /. ~
26.J. Matou? Sek и G. М. Циглер, Топологические нижние границы для хроматического числа: иерархия, Jber. D. Dt. Математика.-Верейн. 106 (2004), 71--90.
27.J. Рифа, Ф. Я. Соловьева и М. Вильянуэва, Self-вложения Хэмминга Штейнера тройных систем малого порядка и APN-перестановок, Des. Коды Cryptogr. (2014), 1- 23.
28.Г. Ringel,? Uber das Problem der Nachbargebiete auf orientierbaren Fl? Achen, Abh. Математика. Sem. Univ. Hamburg 25 (1961), 105-127.
29., Теорема о цветовой карте, Grundlehren der mathematischen Wissenschaften, vol. 209, Springer-Verlag, Berlin, 1974.
30.Г. Рингель и Дж. W. T. Youngs, Решение проблемы раскраски Heawood, Proc. Nat. Acad. Sci. У.S.A. 60 (1968), 438-445.
31.A. Роза, О хроматическом числе тройных систем Штейнера, комбинаторных структурах и их приложениях (Proc. Калгари. Conf., Calgary, 1969), Gordon and Breach, New York, 1970, pp. 369--371.
32., Тройные системы Штейнера и их хроматическое число, Acta Fac. Rerum Natur. Univ. Коменский. Математика. 24 (1970), 159-174.
33.F. Я. Соловьева, Обрезания неориентированных поверхностей тройными системами Штейнера, Проблемы передачи информации 43 (2007), 54--65.
34.D. W. Walkup, Гипотеза нижней границы для 3- и 4-многообразий, Acta Math. 125 (1970), 75--107.
35.D. Цукерман, Линейные экстракторы степеней и неприемлемость максимальной клики и хроматического числа, Theory Comput. Документ № 6, 103-128, только в электронном виде (2007 год).

Эта публикация на других ресурсах

Портал arXiv.org

Другие публикации этой тематики