A note on counting very different sequences

DOI10.1017/S0963548301004783MaRDI QIDQ2777896zbMATH OpenFDO

Authors Emanuela Fachini, János Körner

Publication date 11 September 2002

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548301004783

zbMATH Keywords

graph entropyvery different sequences

Mathematics Subject Classification ID

Extremal set theory (05D05) Measures of information, entropy (94A17)

Review text

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)].

Recommendations

• On the Shannon capacity of probabilistic graphs
• Maximum size of a family of pairwise graph-different permutations
• scientific article; zbMATH DE number 826055
• Forbiddance and capacity
• On the number of independent sets in graphs with fixed independence number

Cited in

(2)

• Distributed broadcast in radio networks of unknown topology.
• scientific article; zbMATH DE number 3890728 (Why is no real title available?)

This page was built for publication: A note on counting very different sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2777896)