Three tutorial lectures on entropy and counting

Abstract

We explain the notion of the {\em entropy} of a discrete random variable, and derive some of its basic properties. We then show through examples how entropy can be useful as a combinatorial enumeration tool. We end with a few open questions.

Notes prepared to accompany a series of tutorial lectures given by the author at the 1st Lake Michigan Workshop on Combinatorics and Graph Theory, Western Michigan University, March 15--16 2014

References in corpus (4)

• Information Inequalities for Joint Distributions, with Interpretations and Applications
• The Bipartite Swapping Trick on Graph Homomorphisms
• An upper bound for the number of perfect matchings in graphs
• A new method for enumerating independent sets of a fixed size in general graphs

Cited by in corpus (12)

• Independent Sets, Matchings, and Occupancy Fractions
• Independent sets in hypergraphs with a forbidden link
• Multicolour containers and the entropy of decorated graph limits
• Notes on use of generalized entropies in counting
• Tight bounds on the coefficients of partition functions via stability
• Learning Altruistic Behaviours in Reinforcement Learning without External Rewards
• PAC Mode Estimation using PPR Martingale Confidence Sequences
• A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs
• Subspace exploration: Bounds on Projected Frequency Estimation
• Chang's lemma via Pinsker's inequality
• On directed analogues of expander and hyperfinite graph sequences
• A Note on Fractional DP-Coloring of Graphs