2025-11-12T10:22:10.394695

A Composition-Based Approach to EKR Problems

Ebrahimi, Taherkhani

Let $\mathcal{A}$ be a family of subsets of a finite set. A subfamily of $\mathcal{A}$ is said to be intersecting when any two of its members contain at least one common element. We say that $\mathcal{A}$ is an Erd{\H o}s-Ko-Rado (EKR) family if, for every element $x$ of the set, the subfamily consisting of all members of $\mathcal{A}$ that contain $x$ has the maximum cardinality among all intersecting subfamilies of $\mathcal{A}$. If these subfamilies are the only maximum intersecting subfamilies of $\mathcal{A}$, then $\mathcal{A}$ is called a strong EKR family. In this article, we introduce a compositional framework to establish the EKR and strong EKR properties in set systems when some subfamilies are known to satisfy the EKR or strong EKR properties. Our method is powerful enough to yield simpler proofs for several existing results, including those derived from Katona's cycle method (1968), Borg and Meagher's admissible ordering method (2016), related results on the family of permutations studied by Frankl and Deza (1977) and the family of perfect matchings of complete graphs of even order investigated by Meagher and Moura (2005). To demonstrate the applicability and effectiveness of our method when other existing methods have not been successful, we show that for every fixed $r$-uniform hypergraph $H$ and all sufficiently large integers $n$, the family of all subhypergraphs of the complete $r$-uniform hypergraph on $n$ vertices that are isomorphic to $H$ satisfies the strong EKR property, where two copies of $H$ are considered intersecting if they share at least one common hyperedge. Moreover, when the structural constraint $H$ is restricted to be a cycle, we establish a series of EKR results for families of cycles in the complete graph $K_n$ and the complete bipartite graph $K_{n,n}$ for a broad range of the parameter $n$.

academic

A Composition-Based Approach to EKR Problems

基本信息

论文ID: 2509.06207
标题: A Composition-Based Approach to EKR Problems
作者: Javad B. Ebrahimi, Ali Taherkhani
分类: math.CO (组合数学)
发表时间: 2025年10月16日 (arXiv v2)
论文链接: https://arxiv.org/abs/2509.06207

摘要

本文研究有限集合的子集族中的相交性质。给定有限集的子集族 $\mathcal{A}$ ，如果其子族中任意两个成员都至少包含一个公共元素，则称该子族为相交族。如果对于集合中的每个元素 $x$ ，包含 $x$ 的所有 $\mathcal{A}$ 成员构成的子族在所有相交子族中具有最大基数，则称 $\mathcal{A}$ 为Erdős-Ko-Rado (EKR)族。如果这些子族是唯一的最大相交子族，则称 $\mathcal{A}$ 为强EKR族。

本文引入了一个组合框架来建立集合系统的EKR和强EKR性质，特别是当某些子族已知满足EKR或强EKR性质时。该方法不仅能为多个现有结果提供更简洁的证明，还能处理其他现有方法无法成功应用的情况。

研究背景与动机

问题背景

Erdős-Ko-Rado定理是极值组合学的基石之一，最初由Erdős、Ko和Rado在1938年证明并于1961年发表。该定理指出，对于 $n \geq 2k$ 的情况， $n$ 元集合的所有 $k$ 子集族具有EKR性质。

研究动机

现有方法的局限性：虽然已有多种证明EKR型结果的方法，如Katona的循环方法、Borg-Meagher的可容许排序方法等，但这些方法在某些情况下存在局限性。特别是，可容许排序的存在是一个强假设，限制了其适用性。
推广需求：研究者希望将EKR型结果推广到其他数学对象，如置换族、向量空间、图的匹配等，但现有方法难以处理一般的结构约束。
方法统一性：需要一个统一的框架来处理各种不同的EKR问题，特别是当环境图被替换为完全超图或结构条件从匹配修改为给定图H的同构副本时。

核心贡献

提出组合框架：引入了一个新的组合方法来从简单的EKR族构造新的EKR族，该方法能够统一处理多种EKR问题。
两个核心引理：
- 组合引理（Composition Lemma）：提供了构造EKR族的一般方法
- G-平衡引理（G-balanced Lemma）：处理具有群作用的情况
新的理论结果：
- 证明了对于每个固定的 $r$ -一致超图 $H$ 和足够大的整数 $n$ ，完全 $r$ -一致超图上所有与 $H$ 同构的子超图族满足强EKR性质
- 建立了完全图 $K_n$ 和完全二部图 $K_{n,n}$ 中循环族的EKR结果
简化现有证明：为多个已知结果提供了更简洁的证明，包括Katona循环方法、Frankl-Deza置换结果等。

方法详解

核心定义

定义1（相交族、EKR和强EKR性质）：

相交族：对于有限集 $X$ 的子集族 $\mathcal{B}$ ，如果对于每对 $A,B \in \mathcal{B}$ 都有 $A \cap B \neq \emptyset$ ，则称 $\mathcal{B}$ 为相交族
EKR族：如果对于任意 $x \in X$ ，包含 $x$ 的所有 $\mathcal{A}$ 成员构成的子族 $\mathcal{A}_x$ 在所有相交子族中具有最大大小
强EKR族：如果每个具有最大大小的相交子族都等于某个 $\mathcal{A}_x$

定义2（正则关系）：设 $L$ 和 $M$ 分别是 $n$ 元集合 $X$ 的 $\ell$ -子集族和 $m$ -子集族。从 $L$ 到 $M$ 的关系 $\sim$ 称为正则的，如果对于任意 $L \in L$ 和 $M \in M$ ，条件 $L \sim M$ 意味着 $L \subseteq M$ 。

定义3（EKR链和特殊EKR链）：三元组 $(L,M,\sim^I)$ 称为EKR链，如果满足：

族 $M$ 是EKR族
对于每个 $M \in M$ 和 $i \in I$ ，族 $L_M^{(i)}$ 是EKR族
对于每个 $M,M' \in M$ 和 $i,j \in I$ ，有 $|L_M^{(i)}| = |L_{M'}^{(j)}| > 0$
对于每个 $L,L' \in L$ ，有 $\sum_{i \in I} |M_L^{(i)}| = \sum_{i \in I} |M_{L'}^{(i)}|$