2021/10/04 by Felix Joos, Jaehoon Kim, Joos, Felix +5
Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Statistical Methods and Inference
paper · doi:10.48550/arxiv.2110.01570
openalex publication_date 2021/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose a k-uniform hypergraph H that satisfies a certain regularity instance (that is, there is a partition of H given by the hypergraph regularity lemma into a bounded number of quasirandom subhypergraphs of prescribed densities). We prove that with high probability a large enough uniform random sample of the vertex set of H also admits the same regularity instance. Here the crucial feature is that the error term measuring the quasirandomness of the subhypergraphs requires only an arbitrarily small additive correction. This has applications to combinatorial property testing. The graph case of the sampling result was proved by Alon, Fischer, Newman and Shapira.