Extremal G-free induced subgraphs of Kneser graphs

2018/01/11 by Alishahi, Meysam, Taherkhani, Ali · 2 citations
#05C75 #05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1801.03972

Abstract

The Kneser graph \rm 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 Erdős-Ko-Rado theorem determines the cardinality and structure of a maximum induced K₂-free subgraph in \rm KG_n,k. As a generalization of the Erdős-Ko-Rado theorem, Erdős proposed a conjecture about the maximum order of an induced K_s+1-free subgraph of \rm KG_n,k. As the best known result concerning this conjecture, Frankl [Journal of Combinatorial Theory, Series A, 2013], when n≥(2s+1)k-s, gave an affirmative answer to this conjecture and also determined the structure of such a subgraph. In this paper, generalizing the Erdős-Ko-Rado theorem and the Erd\H os matching conjecture, we consider the problem of determining the structure of a maximum family A for which \rm KG_n,k[A] has no subgraph isomorphic to a given graph G. In this regard, we determine the size and the structure of such a family provided that n is sufficiently large with respect to G and k. Furthermore, for the case G=K_1,t, we present a Hilton-Milner type theorem regarding above-mentioned problem, which specializes to an improvement of a result by Gerbner et al. [SIAM Journal on Discrete Mathematics, 2012].

Cited by

• Generalizations of the Erdős Matching Conjecture for the t-Matching Number
• s-almost cross-t-intersecting families for finite sets

Related

• A Generalization of the Erdös-Ko-Rado Theorem
• On "stability" in the Erdős-Ko-Rado theorem
• On the stability of some Erdős--Ko--Rado type results
• Stability results on vertex Turán problems in Kneser graphs
• Induced subgraphs of K_r-free graphs and the Erdős--Rogers problem