On an inverse problem of the Erd\H{o}s-Ko-Rado type theorems

MaRDI QIDQ6337991zbMATH OpenFDO

Authors Xiangliang Kong, Gennian Ge

Publication date 3 April 2020

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: A family of subsets $mathcalFsubseteq[n]choosek$ is called intersecting if any two of its members share a common element. Consider an intersecting family, a direct problem is to determine its maximal size and the inverse problem is to characterize its extremal structure and its corresponding stability. The famous ErdH{o}s-Ko-Rado theorem answered both direct and inverse problems and led the era of studying intersection problems for finite sets. In this paper, we consider the following quantitative intersection problem which can be viewed an inverse problem for ErdH{o}s-Ko-Rado type theorems: For $mathcalFsubseteq[n]choosek$, define its emph{total intersection} as $mathcalI(mathcalF)=su{m}_{F_1,F_{2}inmathcalF}|F_{1}cap{F}_2|$. Then, what is the structure of $mathcalF$ when it has the maximal total intersection among all families in $[n]choosek$ with the same family size? Using a pure combinatorial approach, we provide two structural characterizations of the optimal family of given size that maximizes the total intersection. As a consequence, for $n$ large enough and $mathcalF$ of proper size, these characterizations show that the optimal family $mathcalF$ is indeed $t$-intersecting ($tgeq1$). To a certain extent, this reveals the relationship between properties of being intersecting and maximizing the total intersection. Also, we provide an upper bound on $mathcalI(mathcalF)$ for several ranges of $|mathcalF|$ and determine the unique optimal structure for families with sizes of certain values.

This page was built for publication: On an inverse problem of the Erd\H{o}s-Ko-Rado type theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337991)