Abstract
Let H be any hypergraph in which any two edges have at most one vertex in common. We prove that one can assign non-negative real weights to the matchings of H summing to at most |V(H)|, such that for every edge the sum of the weights of the matchings containing it is at least 1. This is a fractional form of the Erdo{combining double acute accent}s-Faber-Lovász conjecture, which in effect asserts that such weights exist and can be chosen 0,1-valued. We also prove a similar fractional version of a conjecture of Larman, and a common generalization of the two.
Original language | English (US) |
---|---|
Pages (from-to) | 155-160 |
Number of pages | 6 |
Journal | Combinatorica |
Volume | 12 |
Issue number | 2 |
DOIs | |
State | Published - Jun 1992 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics
Keywords
- AMS subject classification code (1991): Primary: 05C65, Secondary: 05B40, 05C70