pith. sign in

arxiv: 1802.09871 · v2 · pith:MSCCLJPPnew · submitted 2018-02-27 · 🧮 math.CO

On the random version of the ErdH{o}s matching conjecture

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

The Kneser hypergraph ${\rm KG}^r_{n,k}$ is an $r$-uniform hypergraph with vertex set consisting of all $k$-subsets of $\{1,\ldots,n\}$ and any collection of $r$ vertices forms an edge if their corresponding $k$-sets are pairwise disjoint. The random Kneser hypergraph ${\rm KG}^r_{n,k}(p)$ is a spanning subhypergraph of ${\rm KG}^r_{n,k}$ in which each edge of ${\rm KG}^r_{n,k}$ is retained independently of each other with probability $p$. The independence number of random subgraphs of ${\rm KG}^2_{n,k}$ was recently addressed in a series of works by Bollob{\'a}s, Narayanan, and Raigorodskii (2016), Balogh, Bollob{\'a}s, and Narayanan (2015), Das and Tran (2016), and Devlin and Kahn (2016). It was proved that the random counterpart of the Erd\H{o}s-Ko-Rado theorem continues to be valid even for very small values of $p$. In this paper, generalizing this result, we will investigate the independence number of random Kneser hypergraphs ${\rm KG}^r_{n,k}(p)$. Broadly speaking, when $k$ is much smaller that $n$, we will prove that the random analogue of the Erd\H{o}s matching conjecture is true even for extremely small values of $p$.

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.