Geodesic
Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
Sbornik. Mathematics, Tome 215 (2024) no. 5, pp. 634-657 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Lower and upper bounds are derived for the minimum number of edges in subgraphs of the graph $G(n,3,1)$ induced by $l$ vertices, where $l \sim cn^2$. The results in this work improve the estimates for this quantity that were obtained previously in the case under study. Bibliography: 16 titles.
Keywords: distance graphs, Johnson graphs, extremal graph theory. 
@article{SM_2024_215_5_a2,
     author = {N. A. Dubinin and E. A. Neustroeva and A. M. Raigorodskii and Ya. K. Shubin},
     title = {Lower and upper bounds for the minimum number of edges in some subgraphs of the {Johnson} graph},
     journal = {Sbornik. Mathematics},
     pages = {634--657},
     year = {2024},
     volume = {215},
     number = {5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2024_215_5_a2/}
}
TY  - JOUR
AU  - N. A. Dubinin
AU  - E. A. Neustroeva
AU  - A. M. Raigorodskii
AU  - Ya. K. Shubin
TI  - Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
JO  - Sbornik. Mathematics
PY  - 2024
SP  - 634
EP  - 657
VL  - 215
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/SM_2024_215_5_a2/
LA  - en
ID  - SM_2024_215_5_a2
ER  - 
%0 Journal Article
%A N. A. Dubinin
%A E. A. Neustroeva
%A A. M. Raigorodskii
%A Ya. K. Shubin
%T Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph
%J Sbornik. Mathematics
%D 2024
%P 634-657
%V 215
%N 5
%U http://geodesic.mathdoc.fr/item/SM_2024_215_5_a2/
%G en
%F SM_2024_215_5_a2
N. A. Dubinin; E. A. Neustroeva; A. M. Raigorodskii; Ya. K. Shubin. Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph. Sbornik. Mathematics, Tome 215 (2024) no. 5, pp. 634-657. http://geodesic.mathdoc.fr/item/SM_2024_215_5_a2/

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

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

[3] 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 | DOI | MR | Zbl

[4] J. Balogh, D. Cherkashin and S. Kiselev, “Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs”, European J. Combin., 79 (2019), 228–236 | DOI | MR | Zbl

[5] J. Balogh, R. A. Krueger and Haoran Luo, “Sharp threshold for the Erdős–Ko–Rado theorem”, Random Structures Algorithms, 62:1 (2022), 3–28 | DOI | MR | Zbl

[6] P. A. Ogarok and A. M. Raigorodskii, “On stability of the independence number of a certain distance graph”, Problems Inform. Transmission, 56:4 (2020), 345–357 | DOI | MR | Zbl

[7] P. Frankl and A. Kupavskii, “Intersection theorems for $(-1,0,1)$-vectors”, European J. Combin., 117 (2024), 103830, 9 pp. | DOI | MR | Zbl

[8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10, N. V. Philips' Gloeilampenfabrieken, Eindhoven, Netherlands, 1973, vi+97 pp. | MR | Zbl

[9] L. Lovasz, “On the Shannon capacity of a graph”, IEEE Trans. Inform. Theory, 25:1 (1979), 1–7 | DOI | MR | Zbl

[10] A. E. Brouwer, S. M. Cioabă, F. Ihringer and 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 | DOI | MR | Zbl

[11] Ya. K. Shubin, “On the minimal number of edges in induced subgraphs of special distance graphs”, Math. Notes, 111:6 (2022), 961–969 | DOI | MR | Zbl

[12] F. A. Pushnyakov, “The number of edges in induced subgraphs of some distance graphs”, Math. Notes, 105:4 (2019), 582–591 | DOI | MR | Zbl

[13] F. A. Pushnyakov and A. M. Raigorodskii, “Estimate of the number of edges in special subgraphs of a distance graph”, Math. Notes, 107:2 (2020), 322–332 | DOI | MR | Zbl

[14] Z. Nagy, “A Ramsey-szám egy konstruktív becslése [A certain constructive estimate of the Ramsey number]”, Mat. Lapok, 23 (1972), 301–302 (Hungarian) | MR | Zbl

[15] E. A. Neustroeva and A. M. Raigorodskii, “Estimates of the number of edges in subgraphs of Johnson graphs”, Math. Notes, 115:2 (2024), 224–232 | DOI

[16] R. Ahlswede and G. O. H. Katona, “Graphs with maximal number of adjacent pairs of edges”, Acta Math. Acad. Sci. Hungar., 32:1–2 (1978), 97–120 | DOI | MR | Zbl