Geodesic
New Upper Bounds for the Independence Numbers of Graphs with Vertices in $\{-1,0,1\}^n$ and Their Applications to Problems of the Chromatic Numbers of Distance Graphs
Matematičeskie zametki, Tome 96 (2014) no. 1, pp. 138-147.

Voir la notice de l'article provenant de la source Math-Net.Ru

Upper bounds for the independence numbers in the graphs with vertices at $\{-1, 0,1\}^n$ are improved. Their applications to problems of the chromatic numbers of distance graphs are studied.
Keywords: graph, hypergraph, independence number, chromatic number, distance graph, Hamming distance, Nelson–Erdős–Hadwiger problem. 
@article{MZM_2014_96_1_a11,
     author = {E. I. Ponomarenko and A. M. Raigorodskii},
     title = {New {Upper} {Bounds} for the {Independence} {Numbers} of {Graphs} with {Vertices} in $\{-1,0,1\}^n$ and {Their} {Applications} to {Problems} of the {Chromatic} {Numbers} of {Distance} {Graphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {138--147},
     publisher = {mathdoc},
     volume = {96},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/}
}
TY  - JOUR
AU  - E. I. Ponomarenko
AU  - A. M. Raigorodskii
TI  - New Upper Bounds for the Independence Numbers of Graphs with Vertices in $\{-1,0,1\}^n$ and Their Applications to Problems of the Chromatic Numbers of Distance Graphs
JO  - Matematičeskie zametki
PY  - 2014
SP  - 138
EP  - 147
VL  - 96
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/
LA  - ru
ID  - MZM_2014_96_1_a11
ER  - 
%0 Journal Article
%A E. I. Ponomarenko
%A A. M. Raigorodskii
%T New Upper Bounds for the Independence Numbers of Graphs with Vertices in $\{-1,0,1\}^n$ and Their Applications to Problems of the Chromatic Numbers of Distance Graphs
%J Matematičeskie zametki
%D 2014
%P 138-147
%V 96
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/
%G ru
%F MZM_2014_96_1_a11
E. I. Ponomarenko; A. M. Raigorodskii. New Upper Bounds for the Independence Numbers of Graphs with Vertices in $\{-1,0,1\}^n$ and Their Applications to Problems of the Chromatic Numbers of Distance Graphs. Matematičeskie zametki, Tome 96 (2014) no. 1, pp. 138-147. http://geodesic.mathdoc.fr/item/MZM_2014_96_1_a11/

[1] P. Frankl, R. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1 (1981), 357–368 | DOI | MR | Zbl

[2] 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

[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, “O khromaticheskikh chislakh sfer v evklidovykh prostranstvakh”, Dokl. RAN, 432:2 (2010), 174–177 | MR | Zbl

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

[6] J. Kahn, G. Kalai, “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc. (N.S.), 29:1 (1993), 60–62 | DOI | MR | Zbl

[7] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in Contemporary Mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2008, 202–247 | MR | Zbl

[8] A. M. Raigorodskii, “Vokrug gipotezy Borsuka”, Geometriya i mekhanika, SMFN, 23, RUDN, M., 2007, 147–164 | MR | Zbl

[9] A. M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, Springer, Berlin, 2013, 429–460 | Zbl

[10] A. M. Raigorodskii, “Kontrprimery k gipoteze Borsuka na sferakh malogo radiusa”, Dokl. RAN, 434:2 (2010), 161–163 | MR | Zbl

[11] A. M. Raigorodskii, “O razmernosti v probleme Borsuka”, UMN, 52:6 (1997), 181–182 | DOI | MR | Zbl

[12] A. M. Raigorodskii, “Ob odnoi otsenke v probleme Borsuka”, UMN, 54:2 (1999), 185–186 | DOI | MR | Zbl

[13] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, UMN, 55:2 (2000), 147–148 | DOI | MR | Zbl

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

[15] A. E. Guterman, V. K. Lyubimov, A. M. Raigorodskii, A. S. Usachev, “O chislakh nezavisimosti grafov rasstoyanii s vershinami v $\{-1,0,1\}^n$”, Matem. zametki, 86:5 (2009), 794–796 | DOI | MR | Zbl

[16] A. E. Guterman, V. K. Lyubimov, A. M. Raigorodskii, A. S. Usachev, “O chislakh nezavisimosti distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$: otsenki, gipotezy i prilozheniya k problemam Nelsona–Erdesha–Khadvigera i Borsuka”, Itogi nauki i tekhn. Ser. Sovrem. mat. i ee pril., 65, VINITI, M., 2009, 82–100 | DOI

[17] V. K. Lyubimov, A. M. Raigorodskii, “O nizhnikh otsenkakh chisel nezavisimosti distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Dokl. RAN, 427:4 (2009), 458–460 | MR | Zbl

[18] V. F. Moskva, A. M. Raigorodskii, “Novye nizhnie otsenki chisel nezavisimosti grafov rasstoyanii s vershinami v $\{-1,0,1\}^n$”, Matem. zametki, 89:2 (2011), 319–320 | DOI | MR | Zbl

[19] A. M. Raigorodskii, A. A. Kharlamova, “O sovokupnostyakh $(-1,0,1)$-vektorov s zapreschennymi znacheniyami poparnykh skalyarnykh proizvedenii”, Trudy po vektornomu i tenzornomu analizu, 29, Izd-vo Mosk. un-ta, M., 2013

[20] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007

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

[22] A. M. Raigorodskii, “Problema Borsuka dlya tselochislennykh mnogogrannikov”, Matem. sb., 193:10 (2002), 139–160 | DOI | MR | Zbl

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

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

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

[26] P. K. Agarwal, J. Pach, Combinatorial Geometry, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley Sons, New York, 1995 | MR

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

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

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

[30] 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

[31] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | DOI | MR | Zbl

[32] N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wet., Proc., Ser. A, 54:5 (1951), 371–373 | Zbl