Maximal degrees in subgraphs of Kneser graphs
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:G6V4MQULrecord.jsonopen to challenge →
classification
math.CO
cs.DM
keywords
degreemaximumnon-emptysubgraphschoosefrackneserresults
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.