Abstract

A matrix with the Restricted Isometry Property (RIP) is a central object in compressed sensing theory, and constructing such matrices is a challenging problem. On the other hand, Paley graphs have played a significant role in Ramsey theory, and understanding their structure remains a major open problem in combinatorics and number theory. In this talk, we review these backgrounds and demonstrate that the RIP of certain matrices provides a sharp estimation for the discrepancy of Paley graphs. Under this result, we consequently obtain a sharp estimation of the clique number of Paley graphs as well.

 

Organizer: Shagnik Das (NTU)