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

DOI10.1016/j.dam.2022.07.023zbMath1499.05610arXiv2111.10436OpenAlexW3217052763WikidataQ113877170 ScholiaQ113877170MaRDI QIDQ2081471

Pooya Hatami, Lianna Hambardzumyan, Hamed 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 propertieslabeling schemeimplicit graph representationprobabilistic universal graph conjecturerandomized communication complexityuniversal graph conjecture

Mathematics Subject Classification ID

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

Related Items (1)

Logical labeling schemes

Cites Work

• The communication complexity of addition
• Classification theory and the number of non-isomorphic models.
• Efficient graph representations
• The speed of hereditary properties of graphs
• Perfect dominating sets in the Cartesian products of prime cycles
• Implicat Representation of Graphs
• A note on the Erdős-Hajnal property for stable graphs
• Communication Complexity
• Regularity lemmas for stable graphs
• Unnamed Item
• Unnamed Item

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