Relative Fractional Independence Number and Its Applications
share
We define the relative fractional independence number of two graphs, G and H, as α^*(G|H)=max_Wα(G⊠ W)/α(H⊠ W), where the maximum is taken over all graphs W, G⊠ W is the strong product of G and W, and α denotes the independence number. We give a non-trivial linear program to compute α^*(G|H) and discuss some of its properties. We show that α^*(G|H)≥X(G)/X(H), where X(G) can be the independence number, the zero-error Shannon capacity, the fractional independence number, the Lov'asz number, or the Schrijver's or Szegedy's variants of the Lov'asz number of a graph G. This inequality is the first explicit non-trivial upper bound on the ratio of the invariants of two arbitrary graphs, as mentioned earlier, which can also be used to obtain upper or lower bounds for these invariants. As explicit applications, we present new upper bounds for the ratio of the zero-error Shannon capacity of two Cayley graphs and compute new lower bounds on the Shannon capacity of certain Johnson graphs (yielding the exact value of their Haemers number). Moreover, we show that the relative fractional independence number can be used to present a stronger version of the well-known No-Homomorphism Lemma. The No-Homomorphism Lemma is widely used to show the non-existence of a homomorphism between two graphs and is also used to give an upper bound on the independence number of a graph. Our extension of the No-Homomorphism Lemma is computationally more accessible than its original version.
READ FULL TEXT