Graph pairs and their entropies: Modularity problems (Q5928569): Difference between revisions

If the union of graphs \(F\), \(G\) on the same vertex set is the complete graph then for every probability distribution \(P\), the inequality \(H(F\cup G,P)+H(F\cap G,P)\leq H(F,P)+H(G,P)\) holds if and only if there is no 3-vertex set containing one edge of each of \(F-G\), \(G-F\), and \(F\cap G\), where \(H(G,P)\) is the graph entropy. \(F\) and \(G\) form a supermodular pair if and only if on no subset of the vertex set are \(F\), \(G\) edge-disjoint and imperfect. For this two proofs are given, one based on the description of the graph entropy in terms of the fractional chromatic number.