Hypergraph regularity and random sampling

Suppose that a k‐uniform hypergraph H 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 s...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2023-07, Vol.62 (4), p.956-1015
Main Authors: Joos, Felix, Kim, Jaehoon, Kühn, Daniela, Osthus, Deryk
Format: Article
Language:English
Subjects:
Combinatorial analysis
Error analysis
Graph theory
hypergraph regularity
property testing
Random sampling
Regularity
Vertex sets
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Suppose that a k‐uniform hypergraph H 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.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.21126