We study constant-cost randomized communication problems and relate them to implicit graph representations in structural graph theory. Specifically, constant-cost communication problems correspond to hereditary graph families that admit constant-size adjacency sketches, or equivalently constant-size probabilistic universal graphs (PUGs), and these graph families are a subset of families that admit adjacency labeling schemes of size O(log n), which are the subject of the well-studied implicit graph question (IGQ). We initiate the study of the hereditary graph families that admit constant-size PUGs, with the two (equivalent) goals of (1) understanding randomized constant-cost communication problems, and (2) understanding a probabilistic version of the IGQ. For each family $\mathcal F$ studied in this paper (including the monogenic bipartite families, product graphs, interval and permutation graphs, families of bounded twin-width, and others), it holds that the subfamilies $\mathcal H \subseteq \mathcal F$ are either stable (in a sense relating to model theory), in which case they admit constant-size PUGs, or they are not stable, in which case they do not. The correspondence between communication problems and hereditary graph families allows for a new method of constructing adjacency labeling schemes. By this method, we show that the induced subgraphs of any Cartesian products are positive examples to the IGQ. We prove that this probabilistic construction cannot be derandomized by using an Equality oracle, i.e. the Equality oracle cannot simulate the k-Hamming Distance communication protocol. We also obtain constant-size sketches for deciding $\mathsf{dist}(x, y) \le k$ for vertices $x$, $y$ in any stable graph family with bounded twin-width. This generalizes to constant-size sketches for deciding first-order formulas over the same graphs.
翻译:我们研究的是成本不变的随机通信问题,并将这些问题与结构图理论中的隐含图形表达方式联系起来。具体地说,常价通信问题与世系图形家庭相对应,世系图形家庭接受的是不变大小的相近性草图,或等同的不变大小的概率通用图形(PUGs),而这些图形家庭是接受大小O(log n)的相近标签计划的家庭的子组,这是研究周密的隐含图形问题(IGQ)的主题。我们开始研究世系图家庭,这些家庭接受恒定规模的PUG(PG),其两个(等值)目标:(1) 理解随机大小的固定成本通信问题,以及(2) 理解IGQ的概率版本。对于本文中研究的每个家庭来说, $ math F$(log n) (log n) (log n) 是单一的双向双向的隐含双向图形问题。我们认为, 亚系的基数的基数(silfadi) 和直径直径直径直径直径直径(IQ) 是稳定的,从一种不具有常态的直径直径直径直系的货币解释法的。