Let $G=(U\cup V,E)$ be a bipartite graph where both partitions $U$ and $V$ have size $n$. Let $\mathcal G$ be the set of perfect matchings. A perfect matching of such a bipartite graph can be seen as permutation $\sigma$ such that $u_i$ is matched with $v_{\sigma(i)}$.
Let $d_i = \text{deg}(u_i)$. Bregman's theorem states $$ |\mathcal G| \leq \prod_{i=1}^n (d_i!)^{\frac{1}{d_i}}. $$ Radhakrishnan proves this theorem using entropy. He uniformly takes an arbitrary $\sigma\in\mathcal G$ and acquires $$ H(\sigma(1),\dots,\sigma(n)) = \sum_{i=1}^n H(\sigma(i) \mid \sigma(1),\dots,\sigma(i-1)) \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(1). $$ The conditional entropy $H(\sigma(i)\mid \sigma(1),\dots,\sigma(i-1))$ can be interpreted as a measure of uncertainty about the matching mate of $u_i$ after the mates of $u_1,\dots,u_{i-1}$ have been revealed. Radhakrishnan's idea is to examine $u_1,\dots,u_n$ in a random order $\tau$, where $\tau$ is taken uniformly from $S_n$. So the matching mates are revealed in the order $\sigma(\tau(1)),\sigma(\tau(2)),\dots,\sigma(\tau(n))$. Fix $\tau$. If vertex $u_i$ appears in the $k_i$th place in the ordering $\tau$ then formula (1) becomes $$ H(\sigma(1),\dots,\sigma(n)) = \sum_{i=1}^n H(\sigma(i) \mid \sigma(\tau(1)),\dots,\sigma(\tau(k_i-1))). $$ I do not understand why this is true. Can someone explain this?
Literature:
- Bregman's theorem (https://en.wikipedia.org/wiki/Bregman%E2%80%93Minc_inequality).
- Radhakrishnan's proof (https://www.sciencedirect.com/science/article/pii/S0097316596927272).
- Proofs of the BOOK chapter 37 page 265 (authors: Martin Aigner and Gunter M. Ziegler).