pith. sign in

arxiv: 1502.05692 · v1 · pith:C5UTE7GMnew · submitted 2015-02-19 · 🧮 math.CO

On "stability" in the ErdH{o}s-Ko-Rado theorem

classification 🧮 math.CO
keywords probabilitysetsaboveansweringappearbollobcompletedenote
0
0 comments X
read the original abstract

Denote by $K_p(n,k)$ the random subgraph of the usual Kneser graph $K(n,k)$ in which edges appear independently, each with probability $p$. Answering a question of Bollob\'as, Narayanan, and Raigorodskii,we show that there is a fixed $p<1$ such that a.s. (i.e., with probability tending to 1 as $k \to \infty$) the maximum independent sets of $K_p(2k+1, k)$ are precisely the sets $\{A\in V(K(2k+1,k)): x\in A\}$ ($x\in [2k+1]$). We also complete the determination of the order of magnitude of the "threshold" for the above property for general $k$ and $n\geq 2k+2$. This is new for $k\sim n/2$, while for smaller $k $ it is a recent result of Das and Tran.

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.