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

DOI10.1016/J.DAM.2022.07.023MaRDI QIDQ2081471zbMATH OpenOpenAlexWikidataFDO

Authors Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

Publication date 13 October 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.10436

zbMATH Keywords

hereditary graph propertiesimplicit graph representationlabeling schemeprobabilistic universal graph conjecturerandomized communication complexityuniversal graph conjecture

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

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 $nimesn$ Boolean matrices $M_n$, such that their public-coin randomized communication complexity tends to infinity, while the randomized communication complexity of every $sqrtnimessqrtn$ submatrix of $M_n$ is bounded by a universal constant.

Recommendations

• scientific article; zbMATH DE number 1833411
• Explicit sparse almost-universal graphs for G (n, kn)
• Universality of random graphs
• Sparse universal graphs
• The structure of almost all graphs in a hereditary property

Cites work

• A note on the Erdős-Hajnal property for stable graphs
• Biasing Boolean functions and collective coin-flipping protocols over arbitrary product distributions
• Classification theory and the number of non-isomorphic models.
• Communication Complexity
• Efficient graph representations
• scientific article; zbMATH DE number 1099508 (Why is no real title available?)
• Implicat Representation of Graphs
• Perfect dominating sets in the Cartesian products of prime cycles
• Regularity lemmas for stable graphs
• The communication complexity of addition
• The speed of hereditary properties of graphs

Cited in

(6)

• Logical labeling schemes
• Optimal adjacency labels for subgraphs of Cartesian products
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Randomized communication and implicit graph representations
• Better boosting of communication oracles, or not

This page was built for publication: A counter-example to the probabilistic universal graph conjecture via randomized communication complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2081471)