Tata Institute of Fundamental Research
Bregman's Theorem
Student Seminar
Speaker:
Sagnik Mukhopadhyay
Organiser:
Rakesh Venkat
Date:
Friday, 22 Feb 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Let A be an $n \times n$ boolean matrix, i.e., its entries come from the set $\{0,1\}$. Let $r_i$ denote the number of 1's in the row $i$. Also, let $S$ denote the set of permutations, $\sigma$, on $[n]$ such that $A_{i, \sigma(i)}=1$for all $i \in [n]$. Then the $perm(A)=|S|$. Bregman's theorem is stated as follows:
$$perm(A) \leq \prod_{i\in [n]}(r_i !)^{1/r_i}$$
This upper bounds the number of perfect matchings in a bi-partite graph. We are going to prove it.
| Speaker: | Sagnik Mukhopadhyay |
| Organiser: | Rakesh Venkat |
| Date: | Friday, 22 Feb 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Let A be an $n \times n$ boolean matrix, i.e., its entries come from the set $\{0,1\}$. Let $r_i$ denote the number of 1's in the row $i$. Also, let $S$ denote the set of permutations, $\sigma$, on $[n]$ such that $A_{i, \sigma(i)}=1$for all $i \in [n]$. Then the $perm(A)=|S|$. Bregman's theorem is stated as follows:
$$perm(A) \leq \prod_{i\in [n]}(r_i !)^{1/r_i}$$
This upper bounds the number of perfect matchings in a bi-partite graph. We are going to prove it.
$$perm(A) \leq \prod_{i\in [n]}(r_i !)^{1/r_i}$$
This upper bounds the number of perfect matchings in a bi-partite graph. We are going to prove it.