Geodesic
A Generalization of Kneser Graphs
Matematičeskie zametki, Tome 107 (2020) no. 3, pp. 351-365.

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

Graphs which are analogs of Kneser graphs are studied. The problem of determining the chromatic numbers of these graphs is considered. It is shown that their structure is similar to that of Kneser graphs. Upper and lower bounds for the chromatic numbers of the graphs under examination are obtained. For certain parameter values, an order-sharp estimate of the chromatic numbers is found, and in some cases, the exact value of the quantity in question is determined.
Keywords: Kneser's conjecture, Kneser graphs, topological method. 
@article{MZM_2020_107_3_a2,
     author = {A. V. Bobu and A. E. Kupriyanov and A. M. Raigorodskii},
     title = {A {Generalization} of {Kneser} {Graphs}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {351--365},
     publisher = {mathdoc},
     volume = {107},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2020_107_3_a2/}
}
TY  - JOUR
AU  - A. V. Bobu
AU  - A. E. Kupriyanov
AU  - A. M. Raigorodskii
TI  - A Generalization of Kneser Graphs
JO  - Matematičeskie zametki
PY  - 2020
SP  - 351
EP  - 365
VL  - 107
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2020_107_3_a2/
LA  - ru
ID  - MZM_2020_107_3_a2
ER  - 
%0 Journal Article
%A A. V. Bobu
%A A. E. Kupriyanov
%A A. M. Raigorodskii
%T A Generalization of Kneser Graphs
%J Matematičeskie zametki
%D 2020
%P 351-365
%V 107
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2020_107_3_a2/
%G ru
%F MZM_2020_107_3_a2
A. V. Bobu; A. E. Kupriyanov; A. M. Raigorodskii. A Generalization of Kneser Graphs. Matematičeskie zametki, Tome 107 (2020) no. 3, pp. 351-365. http://geodesic.mathdoc.fr/item/MZM_2020_107_3_a2/

[1] M. Kneser, “Aufgabe 300”, Jahresber. Deutsch., Math. Verein., 58 (1955), 27

[2] L. Lovász, “Kneser's conjecture, chromatic number, and homotopy”, J. Combin. Theory Ser. A, 25:3 (1978), 319–324 | DOI | MR

[3] J. Matoušek, Using the Borsuk–Ulam Theorem, Springer, Berlin, 2003 | Zbl

[4] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369 | DOI | MR

[5] A. M. Raigorodskii, Gipoteza Knezera i topologicheskii metod v kombinatorike, MTsNMO, M., 2011

[6] S. G. Kiselev, A. M. Raigorodskii, “O khromaticheskom chisle sluchainogo podgrafa knezerovskogo grafa”, Dokl. AN, 476:4 (2017), 375–376 | DOI

[7] M. M. Pyaderkin, A. M. Raigorodskii, “O sluchainykh podgrafakh knezerovskogo grafa i ego obobschenii”, Dokl. AN, 470:4 (2016), 384–386 | DOI

[8] A. M. Raigorodskii, “K odnoi teoreme Lovasa o khromaticheskom chisle sfery”, Matem. zametki, 98:3 (2015), 470–471 | DOI | MR

[9] A. Kupavskii, “On random subgraphs of Kneser and Schrijver graphs”, J. Combin. Theory Ser. A, 141:3 (2016), 8–15 | DOI | MR

[10] A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Combin., 25:4 (2018), 4–52 | MR

[11] A. Kupavskii, Sharp Bounds for the Chromatic Number of Random Kneser Graphs, 2018, arXiv: 1810.01161

[12] J. Balogh, D. Cherkashin, S. Kiselev, Coloring General Kneser Graphs and Hypergraphs via High-Discrepancy Hypergraphs, 2018, arXiv: 1805.09394

[13] A. V. Bobu, A. E. Kupriyanov, “O khromaticheskikh chislakh distantsionnykh grafov, blizkikh k knezerovskim”, Probl. peredachi inform., 52:4 (2016), 64–83

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

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

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

[17] A. B. Kupavskii, “O raskraskakh sfer, vlozhennykh v $\mathbb R^n$”, Matem. sb., 202:6 (2011), 83–110 | DOI | MR | Zbl

[18] O. A. Kostina, A. M. Raigorodskii, “O nizhnikh otsenkakh khromaticheskogo chisla sfery”, Dokl. AN, 463:6 (2015), 639 | DOI

[19] D. Cherkashin, A. Kulikov, A. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Discrete Appl. Math., 243 (2018), 125–131 | DOI | MR

[20] A. M. Raigorodskii, D. D. Cherkashin, “O khromaticheskikh chislakh prostranstv maloi razmernosti”, Dokl. AN, 472:1 (2017), 11–12 | DOI

[21] A. M. Raigorodskii, A. A. Sagdeev, “Ob odnoi otsenke v ekstremalnoi kombinatorike”, Dokl. AN, 478:3 (2018), 271–273 | DOI

[22] E. I. Ponomarenko, A. M. Raigorodskii, “Novye verkhnie otsenki chisel nezavisimosti grafov s vershinami v $\{-1,0,1\}^n$ i ikh prilozheniya v zadachakh o khromaticheskikh chislakh distantsionnykh grafov”, Matem. zametki, 96:1 (2014), 138–147 | DOI | MR | Zbl

[23] A. V. Bobu, A. E. Kupriyanov, “Uluchshenie nizhnikh otsenok khromaticheskogo chisla prostranstva s zapreschennymi odnotsvetnymi treugolnikami”, Matem. zametki, 105:3 (2019), 349–363 | DOI

[24] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “O chisle reber odnorodnogo gipergrafa s diapazonom razreshennykh peresechenii”, Probl. peredachi inform., 53:4 (2017), 16–42

[25] A. M. Raigorodskii, A. V. Bobu, A. E. Kupriyanov, “O chisle reber odnorodnogo gipergrafa s diapazonom razreshennykh peresechenii”, Dokl. AN, 475:4 (2017), 365–368 | DOI

[26] A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Asimptoticheskoe issledovanie zadachi o maksimalnom chisle reber odnorodnogo gipergrafa s odnim zapreschennym peresecheniem”, Matem. sb., 207:5 (2016), 17–42 | DOI | MR

[27] P. Frankl, A. Kupavskii, “Erdős–Ko–Rado theorem for $\{0,\pm1\}$-vectors”, J. Combin. Theory Ser. A, 155 (2018), 157–179 | DOI | MR

[28] P. Frankl, A. Kupavskii, “Intersection theorems for $\{0,\pm1\}$-vectors and $s$-cross-intersecting families”, Mosc. J. Comb. Number Theory, 7:2 (2017), 2–21 | MR

[29] P. Frankl, A. Kupavskii, “Families of vectors without antipodal pairs”, Studia Sci. Math. Hungar., 55:2 (2018), 231–237 | DOI | MR

[30] A. M. Raigorodskii, E. A. Shishunov, “O chislakh nezavisimosti nekotorykh distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Dokl. AN, 488:5 (2019), 486–487 | DOI

[31] A. M. Raigorodskii, T. V. Trukhan, “O khromaticheskikh chislakh nekotorykh distantsionnykh grafov”, Dokl. AN, 482:6 (2018), 648–650 | DOI

[32] A. M. Raigorodskii, D. D. Cherkashin, “Ekstremalnye zadachi v raskraskakh gipergrafov”, UMN, 75:1 (451) (2020), 95–154 | DOI

[33] P. Erdős, Ch. Ko, R. Rado, “Intersection theorems for systems of finite sets”, Quart. J. Math. Oxford Ser. (2), 12 (1961), 313–320 | DOI | MR

[34] A. Kupavskii, “Diversity of uniform intersecting families”, European J. Combin., 74 (2018), 39–47 | DOI | MR

[35] P. Frankl, A. Kupavskii, “New inequalities for families without $k$ pairwise disjoint members”, J. Combin. Theory Ser. A, 157 (2018), 427–434 | DOI | MR

[36] A. Kupavskii, D. Zakharov, “Regular bipartite graphs and intersecting families”, J. Combin. Theory Ser. A, 155 (2018), 180–189 | DOI | MR

[37] P. Frankl, A. Kupavskii, “Counting intersecting and pairs of cross-intersecting families”, Combin. Probab. Comput., 27:1 (2018), 60–68 | DOI | MR

[38] P. Frankl, A. Kupavskii, “A size-sensitive inequality for cross-intersecting families”, European J. Combin., 62 (2017), 263–271 | DOI | MR

[39] P. Frankl, A. Kupavskii, “Uniform $s$-cross-intersecting families”, Combin. Probab. Comput., 26:4 (2017), 517–524 | DOI | MR

[40] B. Bollobás, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős–Ko–Rado theorem”, J. Combin. Theory Ser. A, 137 (2016), 64–78 | DOI | MR