Skip to main navigation Skip to Content
Paper IPM / M / 15373  


Abstract:  
The Kneser hypergraph KG^r_n,k is an runiform hypergraph with vertex set consisting of all ksubsets of 1, . . . , n and any collection of r vertices forms an edge if their corresponding ksets 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 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir