Geodesic
TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM
Forum of Mathematics, Sigma, Tome 3 (2015)

Voir la notice de l'article provenant de la source Cambridge University Press

For natural numbers $n,r\in \mathbb{N}$ with $n\geqslant r$, the Kneser graph $K(n,r)$ is the graph on the family of $r$-element subsets of $\{1,\ldots ,n\}$ in which two sets are adjacent if and only if they are disjoint. Delete the edges of $K(n,r)$ with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? We shall answer this question affirmatively as long as $r/n$ is bounded away from $1/2$, even when the probability of retaining an edge of the Kneser graph is quite small. This gives us a random analogue of the Erdős–Ko–Rado theorem, since an independent set in the Kneser graph is the same as a uniform intersecting family. To prove our main result, we give some new estimates for the number of disjoint pairs in a family in terms of its distance from an intersecting family; these might be of independent interest. 
@article{10_1017_fms_2015_21,
     author = {J\'OZSEF BALOGH and B\'ELA BOLLOB\'AS and BHARGAV P. NARAYANAN},
     title = {TRANSFERENCE {FOR} {THE} {ERD\H{O}S{\textendash}KO{\textendash}RADO} {THEOREM}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {3},
     year = {2015},
     doi = {10.1017/fms.2015.21},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.21/}
}
TY  - JOUR
AU  - JÓZSEF BALOGH
AU  - BÉLA BOLLOBÁS
AU  - BHARGAV P. NARAYANAN
TI  - TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM
JO  - Forum of Mathematics, Sigma
PY  - 2015
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.21/
DO  - 10.1017/fms.2015.21
LA  - en
ID  - 10_1017_fms_2015_21
ER  - 
%0 Journal Article
%A JÓZSEF BALOGH
%A BÉLA BOLLOBÁS
%A BHARGAV P. NARAYANAN
%T TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM
%J Forum of Mathematics, Sigma
%D 2015
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.21/
%R 10.1017/fms.2015.21
%G en
%F 10_1017_fms_2015_21
JÓZSEF BALOGH; BÉLA BOLLOBÁS; BHARGAV P. NARAYANAN. TRANSFERENCE FOR THE ERDŐS–KO–RADO THEOREM. Forum of Mathematics, Sigma, Tome 3 (2015). doi: 10.1017/fms.2015.21

Cité par Sources :