Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio

Details Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio

2011-12-28

arxiv.org/abs/1112.6172v1

Mathematics

Combinatorics

Scientific paper

Brown, Nowakowski and Rall defined the ultimate categorical independence ratio of a graph G as A(G)=\lim_{k\to \infty} i(G^{\times k}), where i(G)=\frac{\alpha (G)}{|V(G)|} denotes the independence ratio of a graph G, and G^{\times k} is the k-th categorical power of G. Let a(G)=\max{\frac{|U|}{|U|+|N_G(U)|}: U is an independent set of G}}, where N_G(U) is the neighborhood of U in G. In this paper we answer a question of Alon and Lubetzky, namely we prove that if a(G)\le 1/2 then A(G)=a(G), and if a(G)>1/2 then A(G)=1. We also discuss some other open problems related to A(G) which are immediately settled by this result.

Affiliated with

Also associated with

No associations

Rating

Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Answer to a question of Alon and Lubetzky about the ultimate categorical independence ratio will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32799