|国家预印本平台
首页|Intersection theorems for families of matchings of complete $k$-partite $k$-graphs

Intersection theorems for families of matchings of complete $k$-partite $k$-graphs

Intersection theorems for families of matchings of complete $k$-partite $k$-graphs

来源:Arxiv_logoArxiv
英文摘要

The celebrated {Erdős-Ko-Rado} Theorem states that for $n \geq 2k$ a family $\mathscr{F}$ of $k$ subsets of $[n]$ for which each pair of members of $\mathscr{F}$ have a non-empty intersection has size at most $\binom{n-1}{k-1}$ and for $n >2k$ has exactly this size if and only if it is the family of all $k$-subsets of $[n]$ containing a fixed element $x\in [n]$. Since its discovery, the {Erdős-Ko-Rado} Theorem has be generalised extensively and many variants have been found for structures other than sets. One such variant is for permutations and so-called generalised permutations. These structures are equivalent to $r$-matchings of the complete bipartite graph $K_{n,m}$ with $r \leq \min\{n,m\}$ in a natural way. The culmination of results of several groups of authors constitute an {Erdős-Ko-Rado} Theorem for families of generalised permutations and so for families of $r$-matchings of $K_{n,m}$ for all feasible values of $r,n$ and $m$. In this paper we generalise this by proving an {Erdős-Ko-Rado} Theorem for families of $r$-matchings of complete $k$-partite $k$-graphs, which can be seen as a partial generalisation of the {Erdős-Ko-Rado} Theorem itself. We also prove similar results for $t$-intersecting families, and for families of matchings whose members have sizes from some set of integers $R$, rather than a single size $r$.

Adam Mammoliti

数学

Adam Mammoliti.Intersection theorems for families of matchings of complete $k$-partite $k$-graphs[EB/OL].(2025-06-24)[2025-07-16].https://arxiv.org/abs/1811.07481.点此复制

评论