О хроматическом числе случайного подграфа некоторого дистанционного графа
Автор: Пядеркин М.М., Райгородский А.М.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 4 (40) т.10, 2018 года.
Бесплатный доступ
В работе изучается хроматическое число графа �(�, 3, 1), вершины которого соот- ветствуют 3-элементным подмножествам множества [�] = {1, 2,..., �}, а ребро меж- ду двумя вершинами проводится в том случае, если соответствующие подмножествапересекаются ровно по одному элементу. Этот граф был использован Ларманом и Роджерсом для оценки хроматического числа пространства R�, и недавно Балог,Косточка и Райгородский установили, что хроматическое число этого графа асимп- тотически равно �2/6. Мы рассматриваем случайные подграфы графа �(�, 3, 1), где каждое ребро исходного графа удаляется с него с вероятностью 1/2, независимо от остальных ребер. В работе доказывается, что хроматическое число этого графа с вы-212 log �сокой вероятностью асимптотически равно �.
Случайные графы, хроматическое число, дистанционный граф
Короткий адрес: https://sciup.org/142220458
IDR: 142220458
Список литературы О хроматическом числе случайного подграфа некоторого дистанционного графа
- Nagy Z. A certain constructive estimate of the Ramsey number//Mat. Lapok. 1972. I. 23. P. 301-302.
- Larman D.G. and Rogers C.A. The realization of distances within sets in Euclidean space//Mathematika. 1972. I. 19:1. P. 1-24.
- Balogh J., Kostochka A.V., Raigorodskii A.M. Coloring some finite sets in R�//Discussiones Mathematicae Graph Theory. 2013. I. 33, N 1. P. 25-31.
- Lov´asz L. Kneser’s conjecture, chromatic number, and homotopy//Journal of Combinatorial Theory. Series A. 1978. I. 25(3). P. 319-324.
- Bollob´as B. The chromatic number of random graphs//Combinatorica. 1988. I. 8. P. 49-55.
- Боголюбский Л.И., Гусев А.С., Пядеркин М.М., Райгородский А.М. Числа независимости и хроматические числа случайных подграфов в некоторых последовательностях графов//Матем. сборник. 2015. T. 206. № 10. P. 3-36.
- Гусев А.С. Новая верхняя оценка хроматического числа случайного подграфа дистанционного графа//Матем. заметки. 2015. Вып. 97, № 3. С. 342-349.
- Пядеркин М.М. Числа независимости случайных подграфов некоторого дистанционного графа//Матем. заметки. 2016. Вып. 99, N 2. С. 288-297.
- Frankl P., Fu¨redi Z. Forbidding just one intersection//Journal Combin. Theory A. 1985. I. 39. P. 160-176.
- Erd˝os P., Ko C., Rado R., Intersection theorems for systems of finite sets//Quart. J. Math. Oxford. 1961. I. 12. P. 313-320.
- Bollob´as B., Narayanan B.P., Raigorodskii A.M. On the stability of the Erd˝os-Ko-Rado theorem//J. Comb. Th. Ser. A. 2016. I. 137. P. 64-78.
- Balogh J., Bollob´as B., Narayanan B.P Transference for the Erdo˝s-Ko-Rado theorem//Forum of Mathematics, Sigma. 2015. V. 3.
- Das S., Tran T. A simple removal lemma for large nearly-intersecting families//Electronic Notes in Discrete Mathematics. 2015. I. 49. P. 93-99.
- Devlin P., Kahn J. On «stability» in the the Erd˝os-Ko-Rado theorem//SIAM J. Discrete Math. 2016. I. 30(2). P. 1283-1289.
- Черкашин Д.Д., Райгородский А.М. О хроматических числах пространств малой размерности//Доклады РАН. 2017. Т. 472, № 1. С. 11-12.
