TOPICS
Search

Fractional Edge Cover Number


The fractional edge-cover number rho^*(H) of a finite hypergraph H with no isolated vertices is the minimum total nonnegative weight on its hyperedges such that the weights incident with every vertex sum to at least 1 (Friedgut and Kahn 1998). Thus

 rho^*(H)=min{sum_(e in E(H))lambda_e: lambda_e>=0, sum_(e∋v)lambda_e>=1 for every v in V(H)}.

It is a linear programming relaxation of the edge cover number. Allowing weights can reduce the value. For the triangle graph, weights 1/2 on all three edges give rho^*=3/2, while the edge cover number is 2.

By linear programming duality, the same value is

 rho^*(H)=max{sum_(v in V(H))x_v: x_v>=0, sum_(v in e)x_v<=1 for every e in E(H)}.

For an ordinary graph without isolated vertices, this is its edge-constraint fractional independence number alpha_f(H). The fractional edge-cover number controls the exponent in extremal subgraph counts.


See also

Edge Cover Number, Fractional Independence Number, Hypergraph

Explore with Wolfram|Alpha

References

Friedgut, E. and Kahn, J. "On the Number of Copies of One Hypergraph in Another." Israel J. Math. 105, 251-256, 1998. https://doi.org/10.1007/BF02780332.

Cite this as:

Weisstein, Eric W. "Fractional Edge Cover Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FractionalEdgeCoverNumber.html

Subject classifications