Maximal degrees in subgraphs of Kneser graphs
Maximal degrees in subgraphs of Kneser graphs
复制标题
克内泽图子图中的最大度数
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Kupavskii
中科院分区：
文献类型：
--
作者：
P. Frankl;A. Kupavskii
本文研究了Kneser图KG(n，k)的非空导出子图的最大度。主要结果之一是，对于$k>；k_0$和$n>；64k^2$，当一个非空子图有$m\ge k{n-2\Choose k-2}$点时，它的最大度至少是$\frac 12(1-Frac{k^2}n)m-{n-2\Choose k-2}\ge 0.49m$。这一界限基本上是最好的可能。其中一个中间步骤是得到极大度小的非空子图的结构结果。
In this paper, we study the maximum degree in non-empty induced subgraphs of the Kneser graph $KG(n,k)$. One of the main results asserts that, for $k>k_0$ and $n>64k^2$, whenever a non-empty subgraph has $m\ge k{n-2\choose k-2}$ vertices, its maximum degree is at least $\frac 12(1-\frac {k^2}n) m - {n-2\choose k-2}\ge 0.49 m$. This bound is essentially best possible. One of the intermediate steps is to obtain structural results on non-empty subgraphs with small maximum degree.