Extremal G-free induced subgraphs of Kneser graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:159

Article

Alishahi, Meysam¹  Taherkhani, Ali² 

[1] Shahrood Univ Technol, Fac Math Sci, POB 316-3619995161, Shahrood, Iran

[2] IASBS, Dept Math, Zanjan 4513766731, Iran

关键词: Erdds-Ko-Rado theorem;    Erdos matching conjecture;    (s, t)-union intersecting family;   

DOI  :  10.1016/j.jcta.2018.06.010

来源: Elsevier

【 摘 要 】

The Kneser graph KG(n,k) is a graph whose vertex set is the family of all k-subsets of [n] and two vertices are adjacent if their corresponding subsets are disjoint. The classical Erdos-Ko-Rado theorem determines the cardinality and structure of a maximum induced K-2-free subgraph in KG(n,k). As a generalization of the Erdos-Ko-Rado theorem, Erdos proposed a conjecture about the maximum cardinality of an induced Ks+1-free subgraph of KG(n,k). As the best known result concerning this conjecture, Frankl (2013) [15], when n >= (2s+1)k-8, gave an affirmative answer to this conjecture and also determined the structure of such a subgraph. In this paper, generalizing the Erdos-Ko-Rado theorem and the Erdos matching conjecture, we consider the problem of determining the structure of a maximum family A for which KG(n,k)[A] has no subgraph isomorphic to a given graph G. In this regard, we determine the size and structure of such a family provided that n is sufficiently large with respect to G and k. Furthermore, for the case G = K-1,K-t, we present a Hilton-Milner type theorem regarding above-mentioned problem, which specializes to an improvement of a result by Gerbner et al. (2012) [19]. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free