# Testing $H$-freeness on graphs of bounded expansion

{pause}
## Background on sparse graphs

{pause}
A graph on $n$ vertices contains at most $\frac{n(n-1)}2$ edges.

{pause}
Roughly, being sparse means containing $o(n^2)$ edges.

{pause #sparse-graphs-hierarchy}
#### Sparse graphs hierarchy

> {pause carousel #sparse-hierarchy up="sparse-graphs-hierarchy"}
> ----
> > ![](dessins/sparse_hierarchy.svg)
> ---
> > ![](dessins/sparse_hierarchy_bounded.svg)
> ---
> > ![](dessins/sparse_hierarchy_minor.svg)
> ---
> > ![](dessins/sparse_hierarchy_expansion.svg)
> ---
> > ![](dessins/sparse_hierarchy_treedepth.svg)
> ---
> > ![](dessins/sparse_hierarchy_admissibility.svg)

{#here change-page="sparse-hierarchy"}

{change-page="sparse-hierarchy"}

{change-page="sparse-hierarchy"}

{change-page="sparse-hierarchy"}

{pause up}
## Proving our main result

{pause .theorem title="Humeau, Kanté, Mock, Picavet, Vigny 2025"}
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}
#### A story of reductions

{pause .lemma #story}
Let $H$ and $G$ be graphs {pause}such that $G$ is $\varepsilon$-far from being $H$-free. {pause}
There exists a set $\mathcal H$ of edge-disjoint copies of $H$ in $G$ of cardinality at least $$\frac{\varepsilon|V(G)|}{|E(H)|}=\Omega(|V(G)|).$$

{pause}
*Proof.*

> If the set contains strictly less copies {pause}$\rightarrow$ remove them {pause}$\rightarrow$ at least one copy remains since $G$ is $\varepsilon$-far from $H$-free.

{pause}
**Can testing for $H$-freeness on $G$ be reduced to testing $H$-freeness on $G[\mathcal H]$ ?**

{pause up="story"}

**List of lemmas:** {pause}
- There is a set $\mathcal H$ of many copies of $H$ in $G$, {pause}
- By preserving some degree property, testing on $G$ can be reduced to testing on $G[\mathcal H]$, {pause}
- By considering low treedepth-coloring of graphs of bounded expansion, $G[\mathcal H]$ can be assumed of bounded treedepth.

{pause}
Czumaj and Sohler 2019 can be used to conclude.

{focus="sparse-hierarchy"}

{unfocus}

{pause up}
#### Proof idea for bounded treedepth

{pause}
Family $G_n$ of graphs:

![](dessins/graph_family_treedepth.svg)

{pause #proof-treedepth}
- $G_n$ has treedepth $5$, {pause}
- we test for $P_5$-freeness.

> {pause carousel #treedepth}
> ----
> > ![](dessins/graph_family_treedepth_P.svg)
> ---
> > ![](dessins/graph_family_treedepth_other_paths_1.svg)
> ---
> > ![](dessins/graph_family_treedepth_other_paths_2.svg)
> ---
> > ![](dessins/graph_family_treedepth_P_complete.svg)

- $|\mathcal P|=n$, {pause}
- $G_n$ is far from $P_5$-free.

{pause up="proof-treedepth"}
Probability to find a copy of $P_5$ in $\mathcal P$ {pause}$\rightarrow$ $0$ when $n\to\infty$.

{change-page="treedepth"}

{change-page="treedepth"}

{change-page="treedepth"}

{pause}
Probability to find a copy of $P_5$ in $\overline{\mathcal P}$ {pause} is $\Omega(1)$.

{pause}
$\Rightarrow$: **$P_5$-freeness is testable for the graph family $\{G_n\}_n$.**

{pause}
**$\overline{\mathcal P}$ and $\mathcal P$ share structure[:]{pause}**
- **$u,v,w$ are common vertices of all paths,** {pause}
- **$a_i$ and $b_j$ are in parallel.**

{pause}
**<u>This generalises to bounded treedepth.</u>**