Email this article Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
- Authors: Dubinin N.A.1, Neustroeva E.A.1, Raigorodskii A.M.1,2,3,4, Shubin Y.K.1
-
Affiliations:
- Moscow Institute of Physics and Technology (National Research University)
- Lomonosov Moscow State University
- Adyghe State University
- Buryat State University
- Issue: Vol 215, No 5 (2024)
- Pages: 71-95
- Section: Articles
- URL: https://journal-vniispk.ru/0368-8666/article/view/255925
- DOI: https://doi.org/10.4213/sm10021
- ID: 255925
Cite item
Open Access
Access granted
Subscription Access
Abstract
Получены нижние и верхние оценки минимального числа ребер в индуцированных подграфах с $l$ вершинами графа $G(n,3,1)$, где $l \sim cn^2$. Полученные результаты улучшают ранее доказанные оценки этой величины в данном режиме.Библиография: 16 названий.
About the authors
Nikita Andreevich Dubinin
Moscow Institute of Physics and Technology (National Research University)
Elizaveta Andreevna Neustroeva
Moscow Institute of Physics and Technology (National Research University)without scientific degree, no status
Andrei Mikhailovich Raigorodskii
Moscow Institute of Physics and Technology (National Research University); Lomonosov Moscow State University; Adyghe State University; Buryat State University
Email: mraigor@yandex.ru
ORCID iD: 0000-0001-8614-9612
Scopus Author ID: 6603605028
Doctor of physico-mathematical sciences, Professor
Yakov Konstantinovich Shubin
Moscow Institute of Physics and Technology (National Research University)without scientific degree, no status
References
- P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368
- J. Kahn, G. Kalai, “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc. (N.S.), 29:1 (1993), 60–62
- A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete geometry and algebraic combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109
- J. Balogh, D. Cherkashin, S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236
- J. Balogh, R. A. Krueger, Haoran Luo, “Sharp threshold for the Erdős–Ko–Rado theorem”, Random Structures Algorithms, 62:1 (2022), 3–28
- П. A. Огарок, А. M. Райгородский, “Об устойчивости числа независимости некоторого дистанционного графа”, Пробл. передачи информ., 56:4 (2020), 50–63
- P. Frankl, A. Kupavskii, “Intersection theorems for $(-1,0,1)$-vectors”, European J. Combin., 117 (2024), 103830, 9 pp.
- P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10, N. V. Philips' Gloeilampenfabrieken, Eindhoven, Nethelands, 1973, vi+97 pp.
- L. Lovasz, “On the Shannon capacity of a graph”, IEEE Trans. Inform. Theory, 25:1 (1979), 1–7
- A. E. Brouwer, S. M. Cioabă, F. Ihringer, M. McGinnis, “The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters”, J. Combin. Theory Ser. B, 133 (2018), 88–121
- Я. К. Шубин, “О минимальном числе ребер в индуцированных подграфах специальных дистанционных графов”, Матем. заметки, 111:6 (2022), 929–939
- Ф. А. Пушняков, “О количествах ребер в порожденных подграфах некоторых дистанционных графов”, Матем. заметки, 105:4 (2019), 592–602
- Ф. А. Пушняков, А. М. Райгородский, “Оценка числа ребер в особых подграфах некоторого дистанционного графа”, Матем. заметки, 107:2 (2020), 286–298
- Z. Nagy, “A Ramsey-szam egy konstruktiv becslese [A certain constructive estimate of the Ramsey number]”, Mat. Lapok, 23 (1972), 301–302 (Hungarian)
- Е. А. Неустроева, А. М. Райгородский, “Оценки числа ребер в подграфах графов Джонсона”, Матем. заметки, 115:2 (2024), 266–275
- R. Ahlswede, G. O. H. Katona, “Graphs with maximal number of adjacent pairs of edges”, Acta Math. Acad. Sci. Hungar., 32:1-2 (1978), 97–120
Supplementary files
