Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty

Hendrik Fichtenberger, Pan Peng, Christian Sohler

Introduction

In the field of graph property testing, the central challenge is to determine whether a massive graph possesses a specific structural property—such as being bipartite or triangle-free—by inspecting only a tiny, constant-sized random sample. While a complete combinatorial characterization of testable properties exists for dense graphs (relying on Szemerédi's regularity lemma), the landscape for sparse graphs remains complex.

This paper focuses on the bounded-degree model, where every vertex in a graph of size $n$ has a maximum degree $d$. Specifically, the authors investigate the role of hyperfiniteness—a structural condition where a graph can be decomposed into small, disconnected components by removing a negligible fraction of its edges. The research establishes a fundamental necessity: any infinite graph property that is testable in constant time must contain an infinite hyperfinite subproperty.

The Role of Hyperfiniteness in Testability

Prior research established that all properties are constant-query testable if the underlying graphs are hyperfinite. However, the converse remained an open question: must a testable property itself be hyperfinite?

The authors prove that while a testable property does not need to be hyperfinite in its entirety, it must possess a "universal footprint" of hyperfiniteness.

Theorem 1.2 (Main Result)

Every constant-query testable property of bounded-degree graphs is either finite or contains an infinite hyperfinite subproperty. Furthermore, the complement of every non-trivially testable property also contains an infinite hyperfinite subproperty.

This result implies that even if a property includes highly complex or well-connected graphs (like expanders), it cannot consist solely of such graphs if it is to remain testable. This leads to a significant corollary: any property formed by the infinite intersection of expander graphs (which are inherently non-hyperfinite) is strictly non-testable.

Methodology: Canonical Testers and Blow-up Graphs

To prove these results, the authors employ several advanced techniques from graph limit theory:

  1. Canonical Testers: The authors demonstrate that any constant-query tester can be converted into a "canonical" form. Rather than searching for specific subgraphs, a canonical tester makes decisions based solely on the empirical distribution of $k$-discs—the local neighborhood of a vertex up to distance $k$.
  2. Frequency Preservers: Using results from Noga Alon, the authors show that the $k$-disc distribution of any large graph can be approximated by a constant-sized graph, known as a frequency preserver.
  3. Blow-up Constructions: By creating many disjoint copies of these small frequency preservers, the authors construct "blow-up" graphs. Because these graphs consist of disconnected, constant-sized components, they are inherently hyperfinite.
  4. Iterative Refinement: The authors iteratively construct sequences of graphs that maintain these hyperfinite characteristics while ensuring the canonical tester continues to accept them, thereby proving the existence of the infinite hyperfinite subproperty.

Challenging the Expander Intuition

A common intuition in graph theory is that if a property is not hyperfinite, it must contain expander graphs (graphs that are difficult to partition). The authors disprove this for testable properties through a "Half-and-Half" counterexample.

They construct a testable property consisting of graphs where exactly half the vertices form a single connected component and the other half are isolated. This property is neither hyperfinite nor close to being an expander (as it is always $\Omega(n)$ edges away from being connected). This construction proves that testability can exist in a middle ground between hyperfiniteness and expansion.

A New Structural Partitioning Theorem

Beyond the main result, the paper introduces a novel partitioning theorem (Theorem 5.1) that may have broader applications in combinatorial optimization and graph limits. The theorem states that any bounded-degree graph can be partitioned into a constant number of subsets (plus a small separator set) such that the local $k$-disc distribution remains stable across any subset with small expansion.

This suggests that local neighborhood structures behave predictably across partition boundaries, providing a new tool for designing and analyzing property testers. The authors identify "incompatible $k$-discs"—local structures that cannot coexist within the same connected component—as a promising avenue for future characterization efforts.

Conclusion

This work provides a necessary condition for constant-query testability in sparse graphs: the presence of an infinite hyperfinite subproperty. While a sufficient condition (a full combinatorial characterization) remains the "holy grail" of the field, the introduction of stable $k$-disc partitions and the clarification of the relationship between testability and expansion represent significant progress toward understanding the limits of sublinear-time algorithms.

Summary updated

BibTeX
@inproceedings{fichtenberger2019every,
  author = {Hendrik Fichtenberger and Pan Peng and Christian Sohler},
  title = {{Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty}},
  booktitle = {SODA},
  year = {2019},
  doi = {10.1137/1.9781611975482.45},
}
Figure