A note on counting very different sequences (Q2777896)

Let \(V\) be a finite set and \({\mathcal G}\) be a family of graphs with common vertex set \(V\). Two sequences of length \(n\) from \(V\), \(x_1,x_2,\dots, x_n\) and \(y_1,y_2,\dots, y_n\), are called very different, if for every \(G\in{\mathcal G}\) there exists an \(i\) \((1\leq i\leq n)\), such that \(\{x_i, y_i\}\in G\). Let \(M(n,{\mathcal G})\) denote the maximum number of very different sequences of length \(n\). The main result of the paper is \(M(n,{\mathcal G})\leq \exp[n\cdot\max_P \min_{G\in{\mathcal G}}H(G, P)]\), where \(P\) runs over all probability distributions on \(V\) and \(H(G,P)\) denotes graph entropy. This provides a slightly stronger (non-asymptotic) version of an earlier result of \textit{L. Gargano}, \textit{J. Körner} and \textit{U. Vaccaro} [Graphs Comb. 9, 31-46 (1993; Zbl 0771.05004)].