The Rank-Ramsey Problem and the Log-Rank Conjecture
<|reference_start|>The Rank-Ramsey Problem and the Log-Rank Conjecture: 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. These investigations also open interesting new avenues in Ramsey theory.   We construct two families of Rank-Ramsey graphs exhibiting polynomial separation between order and complement rank. Graphs in the first family have bounded clique number (as low as $41$). These are subgraphs of certain strong products, whose building blocks are derived from triangle-free strongly-regular graphs. Graphs in the second family are obtained by applying Boolean functions to Erd\H{o}s-R\'enyi graphs. Their clique number is logarithmic, but their complement rank is far smaller than in the first family, about $\mathcal{O}(n^{2/3})$. A key component of this construction is our matrix-theoretic view of lifts.   We also consider lower bounds on the Rank-Ramsey numbers, and determine them in the range where the complement rank is $5$ or less. We consider connections between said numbers and other graph parameters, and find that the two best known explicit constructions of triangle-free Ramsey graphs turn out to be far from Rank-Ramsey.<|reference_end|>
@article{beniamini2024the,
    title={The Rank-Ramsey Problem and the Log-Rank Conjecture},
    author={Gal Beniamini, Nati Linial, Adi Shraibman},
    journal={arXiv preprint arXiv:2405.07337},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.07337},
    primaryClass={math.CO cs.CC}
}