CANCELLED: Gal Beniamini (HUJI) — The Rank-Ramsey Problem and the Log-Rank Conjecture

CANCELLED: Gal Beniamini (HUJI) — The Rank-Ramsey Problem and the Log-Rank Conjecture

CANCELLED: Gal Beniamini (HUJI) — The Rank-Ramsey Problem and the Log-Rank Conjecture

Wednesday, August 14, 2024
  • Lecturer: Gal Beniamini
  • Organizer: Chaim Even Zohar
  • Location: 814 Amado
Abstract:
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 main motivation is that their constructions, as well as proofs of their non-existence, are intimately related to the famous log-rank conjecture from the field of communication complexity. In this talk we will present two new constructions of Rank-Ramsey graph families, exhibiting polynomial separation between order and complement rank. The first family are subgraphs of certain strong products, whose building blocks are derived from triangle-free strongly-regular graphs. The second family are obtained by applying Boolean functions to Erdős-Rényi graphs. We will also consider lower bounds on the Rank-Ramsey numbers, and determine them in the range where the complement rank is 5 or less. Joint work with Nati Linial and Adi Shraibman.
Print to PDF