On the ultimate categorical independence ratio

Brown, Nowakowski and Rall defined the ultimate categorical independence ratio of a graph G   as A(G)=limk→∞i(G×k), where i(G)=α(G)|V(G)| denotes the independence ratio of a graph G  , and G×kG×k is the kth categorical power of G  . Let a(G)=max{|U||U|+|NG(U)|:U is an independent set of G}, where NG(U)NG(U) is the neighborhood of U in G  . In this paper we answer a question of Alon and Lubetzky, namely we prove that A(G)=a(G)A(G)=a(G) if a(G)⩽12, and A(G)=1A(G)=1 otherwise. We also discuss some other open problems related to A(G)A(G) which are immediately settled by this result.