کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5776966 | 1413646 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the stability of some ErdÅs-Ko-Rado type results
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the stability of some ErdÅs-Ko-Rado type results On the stability of some ErdÅs-Ko-Rado type results](/preview/png/5776966.png)
چکیده انگلیسی
Consider classical Kneser's graph K(n,r): for two natural numbers r,n such that r⩽nâ2, its vertices are all the subsets of [n]={1,2,â¦,n} of size r, and two such vertices are adjacent if the corresponding subsets are disjoint. The ErdÅs-Ko-Rado theorem states that the size of the largest independent set in this graph is nâ1râ1. Now let us delete each edge of the graph K(n,r) with some fixed probability p independently of each other. Quite surprisingly, the independence number of such random subgraph Kp(n,r) of the graph K(n,r) is, with high probability, the same as the independence number of the initial graph. This phenomenon is called the stability of the independence number. This paper concerns the independence number of random subgraphs of the graph G(n,r,1), which vertices are the same as in the Kneser graph and there is an edge between two vertices if they intersect in exactly one element. We prove the stability result for constant r and p=12. To do that, we show that any sufficiently large independent set in G(n,r,1) has some predefined structure, and this is a result of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 4, April 2017, Pages 822-831
Journal: Discrete Mathematics - Volume 340, Issue 4, April 2017, Pages 822-831
نویسندگان
M.M. Pyaderkin,