Cover and fractional covers

49 Views Asked by At

I have troubles understanding this definition of a fractional cover. It was in the context of graphs and random variables. The $1_V$ stands for the indicator function:

Let $V$ be a finite set and let $(Y_\alpha)_{\alpha\in V}$ be a family of random variables indexed by the set $V$. A family $\{(V_j,w_j)\}_j$ of pairs $(V_j,w_j)$, where $V_j\subset V$ and $w_j\in[0,1]$ is a fractional cover of $V$ if $$\sum_j w_j\mathbb{1}_{V_j}\geq \mathbb{1}_{V}$$ i.e. $$\sum_{j:\alpha \in V_j}w_j \geq 1,\quad\forall \alpha\in V $$

I have a hard time to get an intuition for that. How can I visualize this fractional cover? Why is it an inequality? Does this mean it has overlapping sets (meaning $V_j\cap V_n \neq \emptyset$)? What does the second inquality show?

It also says a cover $\bigcup_{j}V_j=V$ can be seen as a fractional cover with $w_j=1$, which is clear. (Note: in the second inequality the $1$ is not an indicator function...)

1

There are 1 best solutions below

1
On BEST ANSWER

The cover that this is trying to generalize already has overlapping sets: it is a family $\{V_j\}_j$ such that $\bigcup_j V_j = V$, but there is no requirement that $V_i \cap V_j = \emptyset$ when $i \ne j$.

Another way to phrase the condition $\bigcup_j V_j = V$ is that $$\sum_{j} 1_{V_j} \ge 1_V$$ or that $$\sum_{j : \alpha \in V_j} 1 \ge 1 \qquad \forall \alpha \in V.$$ Here's why: in the second of these equations, the sum on the left just counts the number of $V_j$ containing $\alpha$, and so we are asking that for all $\alpha \in V$, there is at least one $V_j$ such that $\alpha \in V_j$. In the first of these equations, we just combine that into an indicator variable expression.

Now the connection should be clear: instead of "include $V_j$ in the family" and "not include $V_j$ in the family", a fractional cover allows us middle ground: we can "fractionally include" $V_j$ with weight $w_j$.

What this means is that if a set $V_j$ is included with weight $w_j<1$, then each of $V_j$'s elements is not covered all the way; it is only $w_j$-covered. Just like in an ordinary cover, we still want each element $\alpha \in V$ to be covered at least once. However, it can (for example) be contained in two sets $V_i, V_j$ with $w_i = \frac12$ and $w_j = \frac12$. Since we want it to be contained at least once, it is fine if $w_i = \frac12$ and $w_j = \frac23$, for example, because $\frac12 + \frac23 \ge 1$. It is also fine for arbitrarily many sets to help cover a single element.