Geodesic
Stability results for vertex Turán problems in Kneser graphs
Dániel Gerbner1 ; Abhishek Methuku2 ; Dániel T. Nagy1 ; Balazs Patkos1 ; Máté Vizer1
1MTA Rényi Institute
2École Polytechnique Fédérale de Lausanne
The electronic journal of combinatorics, Tome 26 (2019) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The vertex set of the Kneser graph $K(n,k)$ is $V = \binom{[n]}{k}$ and two vertices are adjacent if the corresponding sets are disjoint. For any graph $F$, the largest size of a vertex set $U \subseteq V$ such that $K(n,k)[U]$ is $F$-free, was recently determined by Alishahi and Taherkhani, whenever $n$ is large enough compared to $k$ and $F$. In this paper, we determine the second largest size of a vertex set $W \subseteq V$ such that $K(n,k)[W]$ is $F$-free, in the case when $F$ is an even cycle or a complete multi-partite graph. In the latter case, we actually give a more general theorem depending on the chromatic number of $F$.
DOI : 10.37236/8130
Classification : 05D05, 05C12, 05C35
Mots-clés : Erdős-Ko-Rado theorem, Erdős matching conjecture

Dániel Gerbner  1   ; Abhishek Methuku  2   ; Dániel T. Nagy  1   ; Balazs Patkos  1   ; Máté Vizer  1

1 MTA Rényi Institute
2 École Polytechnique Fédérale de Lausanne 
@article{10_37236_8130,
     author = {D\'aniel Gerbner and Abhishek Methuku and D\'aniel T. Nagy and Balazs Patkos and M\'at\'e Vizer},
     title = {Stability results for vertex {Tur\'an} problems in {Kneser} graphs},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {2},
     doi = {10.37236/8130},
     zbl = {1410.05213},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8130/}
}
TY  - JOUR
AU  - Dániel Gerbner
AU  - Abhishek Methuku
AU  - Dániel T. Nagy
AU  - Balazs Patkos
AU  - Máté Vizer
TI  - Stability results for vertex Turán problems in Kneser graphs
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8130/
DO  - 10.37236/8130
ID  - 10_37236_8130
ER  - 
%0 Journal Article
%A Dániel Gerbner
%A Abhishek Methuku
%A Dániel T. Nagy
%A Balazs Patkos
%A Máté Vizer
%T Stability results for vertex Turán problems in Kneser graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8130/
%R 10.37236/8130
%F 10_37236_8130
Dániel Gerbner; Abhishek Methuku; Dániel T. Nagy; Balazs Patkos; Máté Vizer. Stability results for vertex Turán problems in Kneser graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/8130

Cité par Sources :