Cross-intersecting pairs of hypergraphs

摘要

Two hypergraphs H-1, H-2 are called cross-intersecting if e(1) boolean AND e(2) not equal 0 for every pair of edges e(1) is an element of H-1, e2 is an element of H-2. Each of the hypergraphs is then said to block the other. Given integers n, r, m we determine the maximal size of a sub-hypergraph of [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) of size m. The answer involves a self-similar sequence, first studied by Knuth. We also study the same question with ((n)(r)) replacing [n](r). These results yield new proofs of some known Erdos-Ko-Rado type theorems. (C) 2016 Elsevier Inc. All rights reserved.