Hypergraph regularity and random sampling

Felix Joos; Jaehoon Kim; Daniela Kuhn; Deryk Osthus

doi:10.1002/rsa.21126

Hypergraph regularity and random sampling

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

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

10 Downloads (Pure)

Abstract

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 language	English
Number of pages	60
Journal	Random Structures and Algorithms
Early online date	1 Mar 2023
DOIs	https://doi.org/10.1002/rsa.21126
Publication status	E-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.

Access to Document

10.1002/rsa.21126Licence: None: All rights reserved

joosf2022hypergraph
This is the peer reviewed version of the following article:Joos, F., Kim, J., Kühn, D., Osthus, D., Hypergraph regularity and random sampling, Random Struct. Algorithms. (2023), 1– 60, which has been published in final form at https://doi.org/10.1002/rsa.21126. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. This article may not be enhanced, enriched or otherwise transformed into a derivative work, without express permission from Wiley or by statutory rights under applicable legislation. Copyright notices must not be removed, obscured or modified. The article must be linked to Wiley’s version of record on Wiley Online Library and any embedding, framing or otherwise making available the article or pages thereof by third parties from platforms, services and websites other than Wiley Online Library must be prohibited."
Accepted author manuscript, 673 KBLicence: Other (please specify with Rights Statement)

Cite this

@article{528eaecdd15f498d9445a15664e5945b,

title = "Hypergraph regularity and random sampling",

abstract = "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.",

author = "Felix Joos and Jaehoon Kim and Daniela Kuhn and Deryk Osthus",

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. ",

year = "2023",

month = mar,

day = "1",

doi = "10.1002/rsa.21126",

language = "English",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

}

TY - JOUR

T1 - Hypergraph regularity and random sampling

AU - Joos, Felix

AU - Kim, Jaehoon

AU - Kuhn, Daniela

AU - Osthus, Deryk

N1 - 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.

PY - 2023/3/1

Y1 - 2023/3/1

N2 - 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.

AB - 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.

UR - https://arxiv.org/abs/2110.01570

UR - https://onlinelibrary.wiley.com/journal/10982418

U2 - 10.1002/rsa.21126

DO - 10.1002/rsa.21126

M3 - Article

SN - 1042-9832

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

ER -

Hypergraph regularity and random sampling

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this