__
Revision #1 to TR24-013 | 13th March 2024 17:29
__
#### On locally-characterized expander graphs (a survey)

**Abstract:**
We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs.

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 ({\em 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.

**Changes to previous version:**
minor revision: fixing some typos etc

__
TR24-013 | 26th January 2024 15:24
__

#### On locally-characterized expander graphs (a survey)

**Abstract:**
We consider the notion of a local-characterization of an infinite family of unlabeled bounded-degree graphs.

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 ({\em 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.