Combinatorics Seminar

When: Sunday, May 20, 10am Where: Schreiber 309 Speaker: Eyal Lubetzky, Tel Aviv University Title: Shannon capacity and related problems in Information Theory and Ramsey Theory

Abstract:

In his classical paper from 1956, Shannon introduced the notion of a zero-error capacity of a noisy channel, and its corresponding graph parameter, the Shannon capacity of a graph. This well-studied parameter has applications in Theoretical Computer Science, Information Theory and Combinatorics.

Despite a considerable amount of attention over the years, the Shannon capacity remains unknown even for simple graphs, such as the cycle on 7 vertices. While several of Shannon's original problems from 1956 were settled over the years, including the famous ones by Lov\'asz (1979) and by Alon (1998), many intriguing problems remain unanswered. The methods which had been devised in order to derive bounds on the capacity are interesting on their own account, and combine tools in Algebra and Geometry.

In this talk, I will survey several results in this area, focusing on a recent result in Coding Theory. The lecture will include the relevant definitions and background.