Spring 2017

The Independence Number of the Birkhoff Polytope Graph, and Applications to Coding Theory

Thursday, April 13th, 2017 11:00 am12:00 pm

Add to Calendar

I will describe a journey that starts at error correcting codes for distributed storage, and leads to graph labeling, the study of the Birkhoff polytope graph and the representation theory of the symmetric group.
On the technical side, we prove tight bounds for the independence number of the Birkhoff polytope graph, and use it to characterize the alphabet size needed for maximally recoverable codes in grid topologies.
Joint work with Daniel Kane (UCSD) and Sankeerth Rao (UCSD).