Graph powers, Delsarte, Hoffman, Ramsey, and Shannon

The kth p-power of a graph G is the graph on the vertex set V (G) k, where two k-tuples are adjacent iff the number of their coordinates which are adjacent in G is not congruent to 0 modulo p. The clique number of powers of G is polylogarithmic in the number of vertices; thus graphs with small independence numbers in their p-powers do not contain large homogeneous subsets. We provide algebraic upper bounds for the asymptotic behavior of independence numbers of such powers, settling a conjecture of [N. Alon and E. Lubetzky, Combinatorica, 27 ( 2007), pp. 13-33] up to a factor of 2. For precise bounds on some graphs, we apply Delsarte's linear programming bound and Ho. man's eigenvalue bound. Finally, we show that for any nontrivial graph G, one can point out specific induced subgraphs of large p-powers of G with neither a large clique nor a large independent set. We prove that the larger the Shannon capacity of G is, the larger these subgraphs are, and if G is the complete graph, then some p-power of G matches the bounds of the Frankl-Wilson Ramsey construction, and is in fact a subgraph of a variant of that construction.