The Rank-Ramsey Problem and the Log-Rank Conjecture

Gal Beniamini, Nati Linial, Adi Shraibman

A graph is called Rank-Ramsey if (i) Its clique number is small, and (ii) The adjacency matrix of its complement has small rank. We initiate a systematic study of such graphs. Our…