Отправить статью по E-mail Еще раз о разреженных вершинных полуграфах в графах без треугольников
- Авторы: Разборов А.А.1,2
-
Учреждения:
- University of Chicago
- Математический институт им. В.А. Стеклова Российской академии наук
- Выпуск: Том 213, № 1 (2022)
- Страницы: 119-140
- Раздел: Статьи
- URL: https://journal-vniispk.ru/0368-8666/article/view/133422
- DOI: https://doi.org/10.4213/sm9615
- ID: 133422
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Одна из гипотез Эрдёша утверждает, что в каждом графе без треугольников на $n$ вершинах есть индуцированный подграф на $n/2$ вершинах с не более чем $n^2/50$ ребрами. Мы представляем несколько частных результатов в направлении этой гипотезы. Среди прочего установлена новая оценка $27n^2/1024$ на число ребер в общем случае. Мы полностью доказываем гипотезу для графов обхвата $\geq 5$, для графов с числом независимости $\geq 2n/5$, а также для сильно регулярных графов. Каждый из этих трех классов включает обе известные (предположительно) экстремальные конфигурации: цикл на пяти вершинах и граф Петерсена. Библиография: 21 название.
Ключевые слова
Об авторах
Александр Александрович Разборов
University of Chicago; Математический институт им. В.А. Стеклова Российской академии наук
Email: razborov@mi-ras.ru
доктор физико-математических наук, без звания
Список литературы
- J. Balogh, F. C. Clemen, B. Lidicky, Max cuts in triangle-free graphs
- N. Biggs, Strongly regular graphs with no triangles
- A. E. Brouwer, “The uniqueness of the strongly regular graph on 77 points”, J. Graph Theory, 7:4 (1983), 455–461
- F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9:4 (1989), 345–362
- P. Erdős, R. Faudree, J. Pach, J. Spencer, “How to make a graph bipartite”, J. Combin. Theory Ser. B, 45:1 (1988), 86–98
- P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, “A local density condition for triangles”, Discrete Math., 127:1-3 (1994), 153–161
- P. Erdős, E. Győri, M. Simonovits, “How many edges should be deleted to make a triangle-free graph bipartite?”, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. Janos Bolyai, 60, North-Holland, Amsterdam, 1992, 239–263
- P. Erdős, “Problems and results in graph theory and combinatorial analysis”, Proceedings of the 5th British combinatorial conference (Univ. Aberdeen, Aberdeen, 1975), Congressus Numerantium, 15, Utilitas Math., Winnipeg, MB, 1976, 169–192
- P. Erdős, “On some problems in graph theory, combinatorial analysis and combinatorial number theory”, Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, 1–17
- P. Erdős, “Some old and new problems in various branches of combinatorics”, Discrete Math., 165/166 (1997), 227–231
- A. Gewirtz, “Graphs with maximal even girth”, Canadian J. Math., 21 (1969), 915–934
- A. Gewirtz, “The uniqueness of $g(2,2,10,56)$”, Trans. New York Acad. Sci., II Ser., 31:6 (1969), 656–675
- А. Л. Гаврилюк, А. А. Махнев, “О графах Крейна без треугольников”, Докл. РАН, 403:6 (2005), 727–730
- A. Grzesik, “On the maximum number of five-cycles in a triangle-free graph”, J. Combin. Theory Ser. B, 102:5 (2012), 1061–1066
- H. Hatami, J. Hladky, D. Kral, S. Norine, A. Razborov, “Non-three-colourable common graphs exist”, Combin. Probab. Comput., 21:5 (2012), 734–742
- H. Hatami, J. Hladky, D. Kral, S. Norine, A. Razborov, “On the number of pentagons in triangle-free graphs”, J. Combin. Theory Ser. A, 120:3 (2013), 722–732
- P. Kaski, P. Östergard, “There are exactly five biplanes with $k = 11$”, J. Combin. Des., 16:2 (2008), 117–127
- M. Krivelevich, “On the edge distribution in triangle-free graphs”, J. Combin. Theory Ser. B, 63:2 (1995), 245–260
- P. Keevash, B. Sudakov, “Sparse halves in triangle-free graphs”, J. Combin. Theory Ser. B, 96:4 (2006), 614–620
- S. Norin, L. Yepremyan, “Sparse halves in dense triangle-free graphs”, J. Combin. Theory Ser. B, 115 (2015), 1–25
- A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282
Дополнительные файлы
