DIFFERENT CAPACITIES OF A DIGRAPH

Sperner product is the natural generalization of co-normal product to digraphs. For every class of digraphs closed under Sperner product, the cardinality of the largest subgraph from the given class, contained as an induced subgraph in the co-normal powers of a graph G, has an exponential growth. The corresponding asymptotic exponent is the capacity of G with respect to said class of digraphs. We derive upper and lower bounds for these capacities for various classes of digraphs, and analyze the conditions under which they are tight.