Enviar artigo por via de e-mail Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
- Autores: Dubinin N.A.1, Neustroeva E.A.1, Raigorodskii A.M.1,2,3,4, Shubin Y.K.1
-
Afiliações:
- Moscow Institute of Physics and Technology (National Research University)
- Lomonosov Moscow State University
- Adyghe State University
- Buryat State University
- Edição: Volume 215, Nº 5 (2024)
- Páginas: 71-95
- Seção: Articles
- URL: https://ogarev-online.ru/0368-8666/article/view/255925
- DOI: https://doi.org/10.4213/sm10021
- ID: 255925
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
Получены нижние и верхние оценки минимального числа ребер в индуцированных подграфах с $l$ вершинами графа $G(n,3,1)$, где $l \sim cn^2$. Полученные результаты улучшают ранее доказанные оценки этой величины в данном режиме.Библиография: 16 названий.
Palavras-chave
Sobre autores
Nikita Dubinin
Moscow Institute of Physics and Technology (National Research University)
Elizaveta Neustroeva
Moscow Institute of Physics and Technology (National Research University)without scientific degree, no status
Andrei 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 Shubin
Moscow Institute of Physics and Technology (National Research University)without scientific degree, no status
Bibliografia
- 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
Arquivos suplementares
