We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs that contains at most one graph of each size. Such a local-characterization is defined in terms of a finite set of (marked) graphs yielding a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness. We survey the work of Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021), which is pivoted at constructing locally-characterized expander graphs. The construction makes inherent use of the iterative and local nature of the Zig-Zag construction of Reingold, Vadhan, and Wigderson (41st FOCS, 2000). This yields a locally-characterizable graph property that cannot be tested (in the bounded-degree graph model) within a number of queries that does not depend on the size of the graph.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Locally-Characterized Expander Graphs (A Survey)

  • Oded Goldreich

摘要

We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs that contains at most one graph of each size. Such a local-characterization is defined in terms of a finite set of (marked) graphs yielding a generalized notion of subgraph-freeness, which extends the standard notions of induced and non-induced subgraph freeness. We survey the work of Adler, Kohler and Peng (32nd SODA and 36th CCC, 2021), which is pivoted at constructing locally-characterized expander graphs. The construction makes inherent use of the iterative and local nature of the Zig-Zag construction of Reingold, Vadhan, and Wigderson (41st FOCS, 2000). This yields a locally-characterizable graph property that cannot be tested (in the bounded-degree graph model) within a number of queries that does not depend on the size of the graph.