The reviewed record of science sign in
Pith

arxiv: 2004.08718 · v1 · pith:G6V4MQUL · submitted 2020-04-18 · math.CO · cs.DM

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
0
0 comments X
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.