2020/04/03 by Xiangliang Kong, Gennian Ge, Kong, Xiangliang +1
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Theory and Algorithms #Graph theory and applications #Limits and Structures in Graph Theory #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2004.01529
openalex publication_date 2020/04/03 · openalex created_date 2020/04/10 · openalex updated_date 2026/07/28
A family of subsets \F\⊆ [n] choose k is called\nintersecting if any two of its members share a common element. Consider an\nintersecting family, a direct problem is to determine its maximal size and the\ninverse problem is to characterize its extremal structure and its corresponding\nstability. The famous Erd Hos-Ko-Rado theorem answered both direct and\ninverse problems and led the era of studying intersection problems for finite\nsets.\n In this paper, we consider the following quantitative intersection problem\nwhich can be viewed an inverse problem for Erd Hos-Ko-Rado type theorems: For\n\F\⊆ [n] choose k, define its \total intersection as\n\I(\F)=\∑F1,F2\∈ \F|F1\∩ F2|. Then,\nwhat is the structure of \F when it has the maximal total\nintersection among all families in [n] choose k with the same family size?\n Using a pure combinatorial approach, we provide two structural\ncharacterizations of the optimal family of given size that maximizes the total\nintersection. As a consequence, for n large enough and \F of\nproper size, these characterizations show that the optimal family \F\nis indeed t-intersecting (t\≥ 1). To a certain extent, this reveals the\nrelationship between properties of being intersecting and maximizing the total\nintersection. Also, we provide an upper bound on \I(\F) for\nseveral ranges of |\F| and determine the unique optimal structure\nfor families with sizes of certain values.\n