New Upper Bound for the Chromatic Number\\ of a~Random Subgraph of a~Distance Graph

A. S. Gusev

Matematičeskie zametki, Tome 97 (2015) no. 3, pp. 342-349.

Résumé

This paper is related to the classical Hadwiger–Nelson problem dealing with the chromatic numbers of distance graphs in ${\mathbb R}^n$. We consider the class consisting of the graphs $G(n,2s+1,s)=(V(n,2s+1), E(n,2s+1,s))$ defined as follows: \begin{align*} V(n,2s+1)=\{x=(x_1,x_2,\dots,x_n): x_i\in \{0,1\}, \, x_1+x_2+\dots+x_n=2s+1\}, \\ E(n,2s+1,s)=\{\{x,y\}:(x,y)=s\}, \end{align*} where $(x,y)$ stands for the inner product. We study the random graph ${\mathcal G}(G(n,2s+1,s),p)$ each of whose edges is taken from the set $E(n,2s+1,s)$ with probability $p$ independently of the other edges. We prove a new bound for the chromatic number of such a graph.

Détail

Keywords: Hadwiger–Nelson problem, distance graph, random subgraph, chromatic number, Turán number.

Bibliographie

[1] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005 | MR | Zbl

[2] J. Balogh, A. Kostochka, A. Raigorodskii, “Coloring some finite sets in ${\mathbb R}^n$”, Discuss. Math. Graph Theory, 33:1 (2013), 25–31 | DOI | MR | Zbl

[3] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | DOI | MR | Zbl

[4] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty Essays on Geometric Graph Theory, Springer, New York, 2013, 429–460 | MR | Zbl

[5] J. Pach, P. K. Agarwal, Combinatorial Geometry, John Wiley and Sons, New York, 1995 | MR | Zbl

[6] A. M. Raigorodskii, “Problemy Borsuka i Gryunbauma dlya reshetchatykh mnogogrannikov”, Izv. RAN. Ser. matem., 69:3 (2005), 81–108 | DOI | MR | Zbl

[7] A. M. Raigorodskii, “Problema Erdesha–Khadvigera i khromaticheskie chisla konechnykh geometricheskikh grafov”, Matem. sb., 196:1 (2005), 123–156 | DOI | MR | Zbl

[8] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[9] A. M. Raigorodskii, “On the chromatic numbers of spheres in ${\mathbb R}^n$”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

[10] E. I. Ponomarenko, A. M. Raigorodskii, “Uluchshenie teoremy Frankla–Uilsona o chisle reber gipergrafa s zapretami na peresecheniya”, Dokl. RAN, 454:3 (2014), 268–269 | DOI | MR | Zbl

[11] E. I. Ponomarenko, A. M. Raigorodskii, “Novye otsenki v zadache o chisle reber gipergrafa s zapretami na peresecheniya”, Probl. peredachi inform., 49:4 (2013), 98–104 | MR

[12] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of its Creators, Springer, New York, 2009 | MR | Zbl

[13] A. M. Raigorodskii, “Problema Borsuka dlya $(0,1)$-mnogogrannikov i kross-politopov”, Dokl. RAN, 371:5 (2000), 600–603 | MR | Zbl

[14] A. M. Raigorodskii, “Problema Borsuka dlya $(0,1)$-mnogogrannikov i kross-politopov”, Dokl. RAN, 384:5 (2002), 593–597 | MR | Zbl

[15] V. Klee, S. Wagon, Old and New Unsolved Problems in Plane Geometry and Number Theory, Dolciani Math. Exp., 11, Math. Assoc. America, Washington, DC, 1991 | MR | Zbl

[16] A. M. Raigorodskii, “Problemy Borsuka i Gryunbauma dlya nekotorykh klassov mnogogrannikov i grafov”, Dokl. RAN, 388:6 (2003), 738–742 | Zbl

[17] A. M. Raigorodskii, K. A. Mikhailov, “O chislakh Ramseya dlya polnykh distantsionnykh grafov s vershinami v $\{0,1\}^n$”, Matem. sb., 200:12 (2009), 63–80 | DOI | MR | Zbl

[18] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Radio i svyaz, M., 1979 | MR | MR | Zbl

[19] V. Rödl, “On a packing and covering problem”, European J. Combin., 6:1 (1985), 69–78 | DOI | MR | Zbl

[20] L. Bassalygo, G. Cohen, G. Zémor, “Codes with forbidden distances”, Discrete Math., 213:1-3 (2000), 3–11 | DOI | MR | Zbl

[21] P. Erdős, A. Rényi, “On random graphs. I”, Publ. Math. Debrecen, 6 (1959), 290–297 | MR | Zbl

[22] A. M. Raigorodskii, Modeli sluchainykh grafov, MTsNMO, M., 2011

[23] B. Bollobás, Random Graphs, Second edition, Cambridge University Press, 2001 | MR | Zbl

[24] V. F. Kolchin, Sluchainye grafy, Teoriya veroyatnostei i matematicheskaya statistika, Fizmatlit, M., 2000 | MR | Zbl

[25] S. Janson, T. Łuczak, A. Ruciński, Random Graphs, Wiley, New York, 2000 | MR | Zbl

[26] L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov v nekotorykh posledovatelnostyakh grafov”, Dokl. RAN, 457:4 (2014), 383–387 | DOI

[27] L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov nekotorykh distantsionnykh grafov”, Matem. sb. (to appear)

[28] A. B. Kupavskii, “On random subgraphs of Kneser graph”, J. Combin. Theory. Ser. A (to appear)

[29] B. Bollobás, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős–Ko–Rado theorem”, J. Combin. Theory. Ser. A (to appear)

[30] V. E. Tarakanov, Kombinatornye zadachi i $(0,1)$-matritsy, Nauka, M., 1985 | MR | Zbl

[31] A. F. Sidorenko, “What we know and what we do not know about Turán numbers”, Graphs Combin., 11:2 (1995), 179–199 | DOI | MR | Zbl

[32] A. M. Raigorodskii, Sistemy obschikh predstavitelei v kombinatorike i ikh prilozheniya v geometrii, MTsNMO, M., 2009

[33] P. Turán, “Egy gráfelmèleti szélsöértekfeladatrol”, Mat. és Fiz. Lapok, 48:3 (1941), 436–452 | MR | Zbl

[34] B. Bollobás, “The chromatic number of random graphs”, Combinatorica, 8:1 (1988), 49–55 | DOI | MR | Zbl

[35] T. Łuczak, “The chromatic number of random graphs”, Combinatorica, 11:1 (1991), 45–54 | DOI | MR | Zbl

[36] Zs. Baranyai, “On the factorization of the complete uniform hypergraph”, Infinite and Finite Sets, Vol. I, North-Holland, Amsterdam, 1975, 91–108 | MR | Zbl