Cookie Setting MathNet Korea

이전페이지 이동
Property testing for hypergraphs
[2017 Discrete Math 세미나]
Date: 2017-07-27
Speaker : 김재훈 (Birmingham University, UK)
Abstract : We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs). Here, a k-graph property $p$ is testable if there is a randomized algorithm which quickly distinguishes with high probability between k-graphs that satisfy $p$ and those that are far from satisfying $p$. 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.
Information Center for Mathematical Sciences KAIST
34141 대전광역시 유성구 대학로 291 (구성동373-1)
한국과학기술원(KAIST) 수리과학정보센터
전화 042-350-8196
e-mail :
Copyright (C) 2018. ICMS All Rights Reserved.