On intersecting hypergraphs Original Research Article

We investigate the following question: ‘Given an intersecting multi-hypergraph on n points, what fraction of edges must be covered by any of the best 2 points?’ (Here ‘best’ means that together they cover the most.) We call this M2(n). This is a special case of a question asked by Erdös and Gyárfás (1990) (they considered r-wise intersecting and the best t points), and is a generalization of work by Mills (1979) who considered the best single point. These are very hard to calculate in general; we show that determining M2(q2 − q + 1) proves the existence or nonexistence of a projective plane of order q. If such a projective plane exists, we conjecture that M2(q2 + q + 2) = M2(q2 + q + 1). We further show that M2(q2 + q + 3) < M2(q2 + q + 1) and conjecture that M2(n + 2)