“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 15373
School of Mathematics
  Title:   On the random version of the Erdos matching conjecture
  Author(s):  Meysam Alishahi
  Status:   To Appear
  Journal: Discrete Appl. Math.
  Supported by:  IPM
The Kneser hypergraph KG^r_n,k is an r-uniform hypergraph with vertex set consisting of all k-subsets of 1, . . . , n and any collection of r vertices forms an edge if their corresponding k-sets are pairwise disjoint. The random Kneser hypergraph KG^r_n,k(p) is a spanning sub- hypergraph of KG^r_n,k in which each edge of KG^r_n,k is retained independently of each other with probability p. The independence number of random subgraphs of KG^2_n,k was recently addressed in a series of works by Bollobás et al. (2016), Balogh et al. (2015), Das and Tran (2016) and Devlin and Kahn (2016). It was proved that the random counterpart of the Erdő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 KG^r_n,k(p). Broadly speaking, when k is much smaller that n, we will prove that the random analogue of the Erdős matching conjecture is true even for extremely small values of p.

Download TeX format
back to top
scroll left or right