Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 15 / 4 / iii / Solution

Use the same random variables for the edge cover of

G

. For a fixed color vector, any two compatible candidate vertices cannot be adjacent: an edge in a covering graph would force different colors at that coordinate. Thus the compatible candidates form an independent set and there are at most

α

of them. By the maximum entropy on a finite alphabet,

H (X ∣ Y_{1}, \dots, Y_{ℓ}) \leq lo g_{2} α

.

Consequently the mutual information is at least

lo g_{2} n - lo g_{2} α

, while the marginal and conditional-entropy bounds from part (i) make it at most

n^{- 1} \sum_{i} w (G_{i})

. The entropy weight of a graph cover bound follows:

i \sum w (G_{i}) \geq n lo g_{2} (n / α) .

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version