Аннотация:
Работа связана с классической задачей Нелсона–Хадвигера о поиске хроматического числа
дистанционных графов в $\mathbb R^n$. В основном мы рассматриваем класс графов $G(n, r,s)=(V(n, r), E(n,r,s))$, определeнных так:
\begin{gather*}
V(n, r)=\bigl\{\mathbf{x}=(x_1,\dots,x_n) : x_i\in\{0, 1\},\, x_1+\dots+x_n=r\bigr\},
\\
E(n,r,s)=\bigl\{\{\mathbf{x}, \mathbf{y}: (\mathbf{x}, \mathbf{y})=s\}\bigr\},
\end{gather*}
где $(\mathbf{x}, \mathbf{y})$ – евклидово скалярное произведение. В частности, хроматическое число $G(n,3,1)$ недавно было найдено Й. Балогом, А. В. Косточкой, А. М. Райгородским. Мы изучаем случайные подграфы $\mathscr{G}(G(n,r,s), p)$, ребра в которых выбираются независимо из множества $E(n,r,s)$ каждое с вероятностью $p$. Найдены нетривиальные нижние и верхние оценки числа независимости и хроматического числа таких графов. В случае, когда $r-s$ есть степень простого числа и $r\leq 2s+1$, удалось установить порядок $\alpha(\mathscr{G}(G(n,r,s), p))$ и $\chi(\mathscr{G}(G(n,r,s), p))$.
Библиография: 51 название.
Ключевые слова:
случайный граф, дистанционный граф, число независимости, хроматическое число.
Работа выполнена при поддержке Российского фонда фундаментальных исследований (грант № 12-01-00683), гранта Президента РФ МД-6277.2013.1 и Программы Президента РФ поддержки ведущих научных школ (грант № НШ-2519.2012.1).
Образец цитирования:
Л. И. Боголюбский, А. С. Гусев, М. М. Пядёркин, А. М. Райгородский, “Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов”, Матем. сб., 206:10 (2015), 3–36; L. I. Bogolubsky, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Independence numbers and chromatic numbers of the random subgraphs of some distance graphs”, Sb. Math., 206:10 (2015), 1340–1374
\RBibitem{BogGusPya15}
\by Л.~И.~Боголюбский, А.~С.~Гусев, М.~М.~Пядёркин, А.~М.~Райгородский
\paper Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов
\jour Матем. сб.
\yr 2015
\vol 206
\issue 10
\pages 3--36
\mathnet{http://mi.mathnet.ru/sm8344}
\crossref{https://doi.org/10.4213/sm8344}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3438562}
\zmath{https://zbmath.org/?q=an:1331.05191}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2015SbMat.206.1340B}
\elib{https://elibrary.ru/item.asp?id=24850568}
\transl
\by L.~I.~Bogolubsky, A.~S.~Gusev, M.~M.~Pyaderkin, A.~M.~Raigorodskii
\paper Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
\jour Sb. Math.
\yr 2015
\vol 206
\issue 10
\pages 1340--1374
\crossref{https://doi.org/10.1070/SM2015v206n10ABEH004498}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000367229400001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84953283845}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm8344
https://doi.org/10.4213/sm8344
https://www.mathnet.ru/rus/sm/v206/i10/p3
Эта публикация цитируется в следующих 28 статьяx:
Random Struct Algorithms, 62:1 (2023), 3
А. М. Райгородский, В. С. Карась, “Асимптотика числа независимости случайного подграфа
графа $G(n,r,<s)$”, Матем. заметки, 111:1 (2022), 107–116; A. M. Raigorodskii, V. S. Karas, “Asymptotics of the Independence Number of a Random Subgraph of the Graph $G(n,r,<s)$”, Math. Notes, 111:1 (2022), 124–131
Д. А. Захаров, “О хроматических числах некоторых дистанционных графов”, Матем. заметки, 107:2 (2020), 210–220; D. A. Zakharov, “Chromatic Numbers of Some Distance Graphs”, Math. Notes, 107:2 (2020), 238–246
Ф. А. Пушняков, А. М. Райгородский, “Оценка числа ребер в особых подграфах
некоторого дистанционного графа”, Матем. заметки, 107:2 (2020), 286–298; Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332
Mohar B., Wu H., “Fractional Chromatic Number of a Random Subgraph”, J. Graph Theory, 95:3 (2020), 467–472
M. Alishahi, A. Taherkhani, “On the random version of the era's matching conjecture”, Discret Appl. Math., 254 (2019), 1–9
М. М. Пядёркин, “О пороговой вероятности для устойчивости независимых
множеств в дистанционном графе”, Матем. заметки, 106:2 (2019), 280–294; M. M. Pyaderkin, “On Threshold Probability for the Stability of Independent Sets in Distance Graphs”, Math. Notes, 106:2 (2019), 274–285
A. Kupayskii, “Degree versions of theorems on intersecting families via stability”, J. Comb. Theory Ser. A, 168 (2019), 272–287
S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random kneser graphs”, Acta Math. Univ. Comen., 88:3 (2019), 861–865
M. M. Pyaderkin, “On the chromatic number of random subgraphs of a certain distance graph”, Discret Appl. Math., 267 (2019), 209–214
M. Alishahi, H. Hajiabolhassan, “Chromatic number of random Kneser hypergraphs”, J. Combin. Theory Ser. A, 154 (2018), 1–20
А. С. Гусев, “Кликовые числа случайных подграфов некоторых дистанционных графов”, Пробл. передачи информ., 54:2 (2018), 73–85; A. S. Gusev, “Clique numbers of random subgraphs of some distance graphs”, Problems Inform. Transmission, 54:2 (2018), 165–175
A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Comb., 25:4 (2018), P4.52, 16 pp.
M. M. Pyaderkin, “On the stability of some Erdős–Ko–Rado type results”, Discrete Math., 340:4 (2017), 822–831
Д. Д. Черкашин, А. М. Райгородский, “О хроматических числах пространств малой размерности”, Докл. РАН, 472:1 (2017), 11–12; D. D. Cherkashin, A. M. Raigorodskii, “on the Chromatic Numbers of Low-Dimensional Spaces”, Dokl. Math., 95:1 (2017), 5–6
С. Г. Киселев, А. М. Райгородский, “О хроматическом числе случайного подграфа кнезеровского графа”, Докл. РАН, 476:4 (2017), 375–376; S. G. Kiselev, A. M. Raigorodskii, “On the chromatic number of a random subgraph of the Kneser graph”, Dokl. Math., 96:2 (2017), 475–476
А. М. Райгородский, “Об устойчивости числа независимости случайного подграфа”, Докл. РАН, 477:6 (2017), 649–651; A. M. Raigorodskii, “On the stability of the independence number of a random subgraph”, Dokl. Math., 96:3 (2017), 628–630
Н. М. Деревянко, С. Г. Киселев, “Числа независимости случайных подграфов некоторого дистанционного графа”, Пробл. передачи информ., 53:4 (2017), 3–15; N. M. Derevyanko, S. G. Kiselev, “Independence numbers of random subgraphs of some distance graph”, Problems Inform. Transmission, 53:4 (2017), 307–318
L. Iskhakov, M. Mironov, “Diameters of Random Distance Graphs”, J Math Sci, 227:4 (2017), 407
М. М. Пядёркин, “Числа независимости случайных подграфов некоторого дистанционного графа”, Матем. заметки, 99:2 (2016), 288–297; M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319
Цитирование в формате AMSBIB
Обратная связь: