Paper Info
Title
On intersecting hypergraphs
Abstract
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 M 2 ( 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 M 2 ( q 2 − q + 1) proves the existence or nonexistence of a projective plane of order q . If such a projective plane exists, we conjecture that M 2 ( q 2 + q + 2) = M 2 ( q 2 + q + 1). We further show that M 2 ( q 2 + q + 3) < M 2 ( q 2 + q + 1) and conjecture that M 2 ( n + 2)< M 2 ( n ) for all n . We determine the specific values for n ⩽ 10. In particular, we have the surprising result that M 2 (7)= M 2 (8), leading to the conjecture made above. We further conjecture that M 2 (11)= 5 8 and M 2 (12) = 7 12 . To better study this problem, we introduce the concept of fractional matchings and coverings of order 2.
Year
DOI
Venue
1998
10.1016/S0012-365X(97)00136-2
Discrete Mathematics
Keywords
Field
DocType
intersecting hypergraphs,projective plane
Discrete mathematics,Combinatorics,Constraint graph,Projective plane,Conjecture,Mathematics,Special case
Journal
Volume
Issue
ISSN
182
1-3
Discrete Mathematics
Citations 
PageRank 
References 
0
0.34
3
Authors
2
Name
Order
Citations
PageRank
Barry Guiduli1384.66
Zoltán Király213117.24