Talk information

Date: Sunday, March 23, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Igal Sason (Technion)
Title: On Strongly Regular Graphs, the Friendship Theorem, and the Shannon Capacity of Graphs

Abstract:

This talk presents observations on the Lovász $\vartheta$-function, friendship theorem, and Shannon capacity of graphs. Specifically, we derive a simple closed-form expression for the Lovász $\vartheta$-function for all strongly regular graphs and establish upper and lower bounds on that function for all regular graphs. The closed-form expression for strongly regular graphs enables to provide an alternative proof of the celebrated friendship theorem, originally proved by Erdős, Rényi, and Sós (1966). Furthermore, it facilitates the derivation of closed-form bounds on key graph invariants, including the independence number, clique number, and (fractional) chromatic number of strongly regular graphs. We also introduce the concept of Shannon capacity and demonstrate that the closed-form expression of the Lovász $\vartheta$-function allows for an exact determination of the capacity for two infinite subclasses of strongly regular graphs.