Cross-intersecting pairs of hypergraphs

详细信息    查看全文

• 作者：Ron Aharoni^a ; ¹ ; ^{raharoni@gmail.com} ; David Howard^b ; ² ; ^{dmhoward@colgate.edu}
• 关键词：Cross-intersecting hypergraphs ; Erdős&ndash ; Ko&ndash ; Rado ; r-Partite hypergaphs ; Rainbow matchings
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：148
• 期：Complete
• 页码：15-26
• 全文大小：332 K
• 卷排序：148

文摘

Two hypergraphs H1,H2 are called cross-intersecting   if e1∩e2≠∅e1∩e2≠∅ for every pair of edges e1∈H1, e2∈H2e1∈H1, e2∈H2. Each of the hypergraphs is then said to block   the other. Given integers n,r,mn,r,m we determine the maximal size of a sub-hypergraph of [n]r[n]r (meaning that it is r-partite, with all sides of size n  ) for which there exists a blocking sub-hypergraph of [n]r[n]r of size m  . The answer involves a self-similar sequence, first studied by Knuth. We also study the same question with (nr) replacing [n]r[n]r. These results yield new proofs of some known Erdős–Ko–Rado type theorems.