English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

One of the most fundamental questions in graph property testing is tocharacterize the combinatorial structure of properties that are testable with aconstant number of queries. We work towards an answer to this question for thebounded-degree graph model introduced in [Goldreich, Ron, 2002], where theinput graphs have maximum degree bounded by a constant $d$. In this model, itis known (among other results) that every \emph{hyperfinite} property isconstant-query testable [Newman, Sohler, 2013], where, informally, a graphproperty is hyperfinite, if for every $\delta >0$ every graph in the propertycan be partitioned into small connected components by removing $\delta n$edges.  In this paper we show that hyperfiniteness plays a role in \emph{every}testable property, i.e. we show that every testable property is either finite(which trivially implies hyperfiniteness and testability) or contains aninfinite hyperfinite subproperty. A simple consequence of our result is that noinfinite graph property that only consists of expander graphs is constant-querytestable.  Based on the above findings, one could ask if every infinite testablenon-hyperfinite property might contain an infinite family of expander (ornear-expander) graphs. We show that this is not true. Motivated by ourcounter-example we develop a theorem that shows that we can partition the setof vertices of every bounded degree graph into a constant number of subsets anda separator set, such that the separator set is small and the distribution of$k$-disks on every subset of a partition class, is roughly the same as that ofthe partition class if the subset has small expansion.

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