Maximum degree and fractional matchings in uniform hypergraphs
Author(s) -
Zoltán Füredi
Publication year - 1981
Publication title -
combinatorica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.106
H-Index - 58
eISSN - 1439-6912
pISSN - 0209-9683
DOI - 10.1007/bf02579271
Subject(s) - mathematics , combinatorics , hypergraph , degree (music) , corollary , projective plane , discrete mathematics , geometry , correlation , physics , acoustics
Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= $$\mathop {\max }\limits_{x \in X} $$ |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom