Abstract:
This work is concerned with the Nelson-Hadwiger classical\linebreak problem of finding the chromatic numbers of distance graphs in Rn. Most consideration is given to the class of graphs G(n,r,s)=(V(n,r),E(n,r,s)) defined as follows:
V(n,r)={x=(x1,…,xn):xi∈{0,1},x1+⋯+xn=r},E(n,r,s)={{x,y:(x,y)=s}},
where (x,y) is the Euclidean inner product. In particular, the chromatic number of G(n,3,1) was recently found by Balogh, Kostochka and Raigorodskii. The objects of the study are the random subgraphs G(G(n,r,s),p) whose edges are independently taken from the set E(n,r,s), each with probability p. The independence number and the chromatic number of such graphs are estimated both from below and from above. In the case when r−s is a prime power and r≤2s+1, the order of growth of α(G(G(n,r,s),p)) and χ(G(G(n,r,s),p)) is established.
Bibliography: 51 titles.
Keywords:
random graph, distance graph, independence number, chromatic number.
This work was supported by the Russian Foundation for Basic Research (grant no. 12-01-00683) and by the Council of the President of the Russian Federation for the Support of Young Russian Scientists and Leading Scientific Schools, grant nos. МД-6277.2013.1 and НШ-2519.2012.1.
Citation:
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
\Bibitem{BogGusPya15}
\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
\mathnet{http://mi.mathnet.ru/eng/sm8344}
\crossref{https://doi.org/10.1070/SM2015v206n10ABEH004498}
\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}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000367229400001}
\elib{https://elibrary.ru/item.asp?id=24850568}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84953283845}
Linking options:
https://www.mathnet.ru/eng/sm8344
https://doi.org/10.1070/SM2015v206n10ABEH004498
https://www.mathnet.ru/eng/sm/v206/i10/p3
This publication is cited in the following 28 articles:
Random Struct Algorithms, 62:1 (2023), 3
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
D. A. Zakharov, “Chromatic Numbers of Some Distance Graphs”, Math. Notes, 107:2 (2020), 238–246
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
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
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
D. D. Cherkashin, A. M. Raigorodskii, “on the Chromatic Numbers of Low-Dimensional Spaces”, Dokl. Math., 95:1 (2017), 5–6
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
A. M. Raigorodskii, “On the stability of the independence number of a random subgraph”, Dokl. Math., 96:3 (2017), 628–630
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
M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319