Back to Search Start Over

Maximal degrees in subgraphs of Kneser graphs

Authors :
Frankl, Peter
Kupavskii, Andrey
Publication Year :
2020

Abstract

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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2004.08718
Document Type :
Working Paper