Multi-part cross-intersecting families

2018/09/24 by Xiangliang Kong, Kong, Xiangliang, Yuanxiao Xi +3
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1809.08756

openalex publication_date 2018/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let A⊆[n]\choose a and B⊆[n]\choose b be two families of subsets of [n], we say A and B are cross-intersecting if A∩ B≠ ∅ for all A\inA, B\inB. In this paper, we study cross-intersecting families in the multi-part setting. By characterizing the independent sets of vertex-transitive graphs and their direct products, we determine the sizes and structures of maximum-sized multi-part cross-intersecting families. This generalizes the results of Hilton's and Frankl--Tohushige's on cross-intersecting families in the single-part setting.

Related

• The maximum sum of sizes of cross-intersecting families of subsets of a set
• Non-empty pairwise cross-intersecting families
• Non-trivially intersecting multi-part families
• Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
• The maximum product of sizes of cross-t-intersecting uniform families