Hypergraph regularity and random sampling

Felix Joos, Jaehoon Kim*, Daniela Kuhn, Deryk Osthus

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)


Suppose that a -uniform hypergraph satisfies a certain regularity instance (that is, there is a partition of 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 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.
Original languageEnglish
Number of pages60
JournalRandom Structures and Algorithms
Early online date1 Mar 2023
Publication statusE-pub ahead of print - 1 Mar 2023

Bibliographical note

Note by email on 9.3. from Tom Gilbert Open Access Officer Library Services (in an email to D Osthus): It is the submission date that is used to determine whether a paper is to be assessed against the current or former UKRI OA policy.

With the paper having been received by Wiley on 5th October 2021, it is assessed against the former policy.

Random Structures & Algorithms applies a 12 month embargo, which is permissible for papers acknowledging EPSRC (under the former UKRI OA policy) – so this paper is compliant with funder OA requirements.


Dive into the research topics of 'Hypergraph regularity and random sampling'. Together they form a unique fingerprint.

Cite this