Abstract
For a hypergraph ℋ andb:ℋ→ℝ+ define
Conjecture. There is a matching ℳ of ℋ such that
For uniform ℋ andb constant this is the main theorem of [4]. Here we prove the conjecture if ℋ is uniform or intersecting, orb is constant.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. Berge: Packing problems and hypergraph theory: a survey,Ann. Discrete Math. 4 (1979), 3–37.
B. Bollobás:Extremal Graph Theory, Academic Press, New York/London, 1978.
V. Faber andL. Lovász: Problem 18 in: Hypergraph Seminar (Ohio State Univ., 1972),Lecture Notes in Mathematics 411 p. 284. C. Berge and D. K. Ray-Chaudhuri, Eds., Springer-Verlag, Berlin/New York, 1974.
Z. Füredi: Maximum degree and fractional matchings in uniform hypergraphs,Combinatorica 1 (1981), 155–162.
Z. Füredi: Matchings and covers in hypergraphs,Graphs and Combinatorics 4 (1988), 115–206.
L. Lovász:Combinatorial Problems and Exercises, Pakadémiai Kiadó, Budapest North-Holland, Amsterdam, 1979.
L. Lovász: Graph theory and integer programming,Ann. Discrete Math 4 (1979), 141–158.
C. Shannon: A theorem on coloring the lines of a network,J. Math. Physics 28 (1949), 148–151.
Author information
Authors and Affiliations
Additional information
The research was done while the author visited the Department of Mathematics at Rutgers University. Research supported in part by the Hungarian National Science Foundation under grant No. 1812
Supported in party by NSF and AFOSR grants and by a Sloan Research Fellowship
Rights and permissions
About this article
Cite this article
Füredi, Z., Kahn, J. & Seymour, P.D. On the fractional matching polytope of a hypergraph. Combinatorica 13, 167–180 (1993). https://doi.org/10.1007/BF01303202
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01303202