Еще раз о разреженных вершинных полуграфах в графах без треугольников
| Autor: | Alexander Alexandrovich Razborov |
|---|---|
| Rok vydání: | 2021 |
| Zdroj: | Математический сборник. 213:119-140 |
| ISSN: | 2305-2783 0368-8666 |
| Popis: | Одна из гипотез Эрдeша утверждает, что в каждом графе без треугольников на $n$ вершинах есть индуцированный подграф на $n/2$ вершинах с не более чем $n^2/50$ ребрами. Мы представляем несколько частных результатов в направлении этой гипотезы. Среди прочего установлена новая оценка $27n^2/1024$ на число ребер в общем случае. Мы полностью доказываем гипотезу для графов обхвата $\geq 5$, для графов с числом независимости $\geq 2n/5$, а также для сильно регулярных графов. Каждый из этих трех классов включает обе известные (предположительно) экстремальные конфигурации: цикл на пяти вершинах и граф Петерсена. Библиография: 21 название. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|