کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655203 1632935 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the stability of the Erdős–Ko–Rado theorem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the stability of the Erdős–Ko–Rado theorem
چکیده انگلیسی

Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as an intersecting (uniform) family, this gives us a random analogue of the Erdős–Ko–Rado theorem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 137, January 2016, Pages 64–78
نویسندگان
, , ,