On the capacity of boolean graph formulæ

In a recent paper we have solved several well-known combinatorial problems treating them as special cases of our generalization of Shannon's notion of graph capacity. We present a new simple formalism to deal with all such problems in a unified manner, considering graphs or families of graphs as special formulæ the variables of which are pairs of vertices of their common vertex sets. In all of these problems, the maximum size of a set ofn-length sequences from a fixed alphabet is to be determined under various restrictions on the element pairs present in the same coordinate of any two sequences from the set. For sufficiently homogeneous formulæ capacity becomes computable.New applications include generalizations of our result on the maximum number of pairwise qualitatively independentk-partitions of ann-set from independence to various forms of qualitative dependence.Work partially supported by the Italian Ministry of the University and Scientific Research, Project: Algoritmi, Modelli di Calcolo e Strutture Informative.