A counter-example to the probabilistic universal graph conjecture via randomized communication complexity

2021/11/19 by Lianna Hambardzumyan, Hamed Hatami, Hambardzumyan, Lianna +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2111.10436

7 pages

openalex publication_date 2021/11/19 · arxiv created 2021/12/08 · arxiv updated 2021/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal graph if and only if it is stable and has at most factorial speed. Our counter-example follows from the existence of a sequence of n × n Boolean matrices M_n, such that their public-coin randomized communication complexity tends to infinity, while the randomized communication complexity of every √(n)× √(n) submatrix of M_n is bounded by a universal constant.

Cited by

• Sign-Rank of k-Hamming Distance is Constant

Related

• Randomized Communication and Implicit Graph Representations
• Probabilistic communication complexity over the reals
• Universal Communication, Universal Graphs, and Graph Labeling
• Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
• Pseudodeterministic Communication Complexity