Property testing for hypergraphs

Jaehoon Kim (김재훈)

School of Mathematics, Birmingham University, UK

School of Mathematics, Birmingham University, UK

2017/7/27 Thu 4PM-5PM

We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs).

Here, a k-graph property 𝒫 is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy 𝒫 and those that are far from satisfying 𝒫. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.

Here, a k-graph property 𝒫 is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy 𝒫 and those that are far from satisfying 𝒫. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. This is joint work with Felix Joos, Deryk Osthus and Daniela Kühn.