# Graph property testing

{pause}
## Definitions

{pause #being-far}
A graph $G$ is called **$\varepsilon$-far** ($\varepsilon>0$) from satisfying a property $P$ {pause}if at least a proportion $\varepsilon$ of its **representation** {pause}has to be modified to obtain a graph satisfying $P$.

{pause .example title="Discrete graph"}
> $P=\{G\mid~G\text{ contains no edges}\}$; {pause}$G$ far from $P$ $\Rightarrow$ $G$ contains a lot of edges.
>
> {pause}
> **Algorithm idea:** take a random vertex of $G$; answer yes if isolated, no otherwise.
>
> {pause}
> ($G$ far from containing a structure $S$ {pause}(edge, triangle, subgraph, etc) $\Rightarrow$ $G$ contains many disjoint copies of $S$.)

{pause #vocabulary}
**Vocabulary:** {pause}
- Algorithms $\rightarrow$ **testers**, {pause}
- Input access $\rightarrow$ **queries** to an **oracle**, {pause}
- Number of queries $\rightarrow$ **query complexity**.

{pause up="being-far"}
**Output constraint:** {pause}$T$ a tester. {pause}
- $G$ satisfies $P$ $\Rightarrow$ $T(G)$ outputs $1$, {pause}
- $G$ $\varepsilon$-far from satisfying $P$ $\Rightarrow$ $T(G)$ outputs $0$ with probability $\ge 2/3$.

{pause .definition}
$P$ is called **testable** on a graph class $\mathcal C$[,]{pause} if testers (on $\mathcal C$) exist for any $\varepsilon>0$.

{focus="tester-drawing"}

{change-page="tester-drawing"}

{change-page="tester-drawing"}

{change-page="tester-drawing"}

{change-page="tester-drawing"}

{unfocus}

{pause #missing up="vocabulary"}
#### Missing: {pause}
- graph representation, {pause}
- possible queries.

{pause}
Setting these defines a particular **model** of property testing.

{pause up="missing" #models}
## Models

{pause}
#### <u>The dense model</u> (Goldreich, Goldwasser, and Ron 1998)

{pause}
**Graph representation:** {pause}adjacency matrix.

{pause}
**Query:** {pause}"given two integers $i$ and $j$, are the $i$th and $j$th vertices adjacent ?"

{pause #bounded-degree-model}
#### <u>The bounded degree model</u> (Goldreich and Ron 2002)

{pause}
**Graph representation:** {pause}bounded length incidence list.

{pause}
**Query:** {pause}"given two integers $i$ and $j$, give me $i$th neighbour of the $j$th vertex ?"

{carousel up="bounded-degree-model" #graph-models}
----
> {pause}
> #### <u>The general graph model</u> (Parnas and Ron 2002)
>
> {pause}
> **Graph representation:** {pause}incidence list.
>
> {pause}
> **Queries:** {pause}"what is the degree of the $i$th vertex ?", {pause}or "what is the $j$th neighbour of the $i$th vertex ?", {pause}or "are the $i$th and $j$th vertices adjacent ?".
---
>
> #### <u>The random neighbour oracle model</u> (Czumaj and Sohler 2019)
>
> **Graph representation:** incidence list.
>
> **Random neighbour query:** "give me a neighbour of the $i$th vertex, uniformly at random."

{change-page="graph-models"}

{pause carousel #theorem-czumaj}
----
> {.theorem title="Czumaj & Sohler, 2019"}
> For every graph $H$, the property of being **$H$-free** is testable with constant query complexity on **planar graphs** in the random neighbour oracle model.
---
> {.theorem title="Czumaj & Sohler, 2019"}
> For every graph $H$, the property of being **$H$-free** is testable with constanct query complexity on **graph classes excluding a minor** in the random neighbour oracle model.

{change-page="theorem-czumaj"}

{pause up="graph-models"}

## Our main contribution
{pause .theorem title="Humeau, Kanté, Mock, Picavet, Vigny 2025" #our-theorem}
For every graph $H$, the property of being **$H$-free** is testable with constant query complexity on **graph classes of bounded expansion** in the random neighbour oracle model.

{pause}
#### Testers shapes

{pause}
Random **Breadth-First Search** with bounds $d,t$ on both the **breadth** and the **depth**.

{pause up="our-theorem"}
![](./dessins/algo.png){width="646px" height="348px"}

{pause}
In property testing, algorithms are obvious, proofs are involved.