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!
cited_by cdi_FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43
cites cdi_FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43
container_end_page 1015
container_issue 4
container_start_page 956
container_title Random structures & algorithms
container_volume 62
creator Joos, Felix
Kim, Jaehoon
Kühn, Daniela
Osthus, Deryk
description 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.
doi_str_mv 10.1002/rsa.21126
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2817231573</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2817231573</sourcerecordid><originalsourceid>FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43</originalsourceid><addsrcrecordid>eNp1kMtOwzAQRS0EEqWw4A8iseoirT2OH1lWFbRIlZB4rC2ntkOqvLAbofw9LmHLZmYWZ2auDkL3BC8JxrDyQS-BEOAXaEZwLlPIiLw8zxmkuaRwjW5COGKMBQU6Q4vd2Ftfet1_Jt6WQ619dRoT3ZrEx9I1SdBNX1dteYuunK6Dvfvrc_Tx9Pi-2aX7l-3zZr1PD5QCTynX3ElNmOayMEAzbqRh2AjsuBXArDN5RgCMw5QXhWGUGWNEZmM4zYuMztHDdLf33ddgw0kdu8G38aUCSQRQwgSN1GKiDr4LwVunel812o-KYHU2oaIJ9WsisquJ_a5qO_4Pqte39bTxAye4Xko</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2817231573</pqid></control><display><type>article</type><title>Hypergraph regularity and random sampling</title><source>Wiley-Blackwell Read &amp; Publish Collection</source><creator>Joos, Felix ; Kim, Jaehoon ; Kühn, Daniela ; Osthus, Deryk</creator><creatorcontrib>Joos, Felix ; Kim, Jaehoon ; Kühn, Daniela ; Osthus, Deryk</creatorcontrib><description>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.</description><identifier>ISSN: 1042-9832</identifier><identifier>EISSN: 1098-2418</identifier><identifier>DOI: 10.1002/rsa.21126</identifier><language>eng</language><publisher>New York: John Wiley &amp; Sons, Inc</publisher><subject>Combinatorial analysis ; Error analysis ; Graph theory ; hypergraph regularity ; property testing ; Random sampling ; Regularity ; Vertex sets</subject><ispartof>Random structures &amp; algorithms, 2023-07, Vol.62 (4), p.956-1015</ispartof><rights>2023 Wiley Periodicals LLC.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43</citedby><cites>FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Joos, Felix</creatorcontrib><creatorcontrib>Kim, Jaehoon</creatorcontrib><creatorcontrib>Kühn, Daniela</creatorcontrib><creatorcontrib>Osthus, Deryk</creatorcontrib><title>Hypergraph regularity and random sampling</title><title>Random structures &amp; algorithms</title><description>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.</description><subject>Combinatorial analysis</subject><subject>Error analysis</subject><subject>Graph theory</subject><subject>hypergraph regularity</subject><subject>property testing</subject><subject>Random sampling</subject><subject>Regularity</subject><subject>Vertex sets</subject><issn>1042-9832</issn><issn>1098-2418</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2023</creationdate><recordtype>article</recordtype><recordid>eNp1kMtOwzAQRS0EEqWw4A8iseoirT2OH1lWFbRIlZB4rC2ntkOqvLAbofw9LmHLZmYWZ2auDkL3BC8JxrDyQS-BEOAXaEZwLlPIiLw8zxmkuaRwjW5COGKMBQU6Q4vd2Ftfet1_Jt6WQ619dRoT3ZrEx9I1SdBNX1dteYuunK6Dvfvrc_Tx9Pi-2aX7l-3zZr1PD5QCTynX3ElNmOayMEAzbqRh2AjsuBXArDN5RgCMw5QXhWGUGWNEZmM4zYuMztHDdLf33ddgw0kdu8G38aUCSQRQwgSN1GKiDr4LwVunel812o-KYHU2oaIJ9WsisquJ_a5qO_4Pqte39bTxAye4Xko</recordid><startdate>202307</startdate><enddate>202307</enddate><creator>Joos, Felix</creator><creator>Kim, Jaehoon</creator><creator>Kühn, Daniela</creator><creator>Osthus, Deryk</creator><general>John Wiley &amp; Sons, Inc</general><general>Wiley Subscription Services, Inc</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>202307</creationdate><title>Hypergraph regularity and random sampling</title><author>Joos, Felix ; Kim, Jaehoon ; Kühn, Daniela ; Osthus, Deryk</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2023</creationdate><topic>Combinatorial analysis</topic><topic>Error analysis</topic><topic>Graph theory</topic><topic>hypergraph regularity</topic><topic>property testing</topic><topic>Random sampling</topic><topic>Regularity</topic><topic>Vertex sets</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Joos, Felix</creatorcontrib><creatorcontrib>Kim, Jaehoon</creatorcontrib><creatorcontrib>Kühn, Daniela</creatorcontrib><creatorcontrib>Osthus, Deryk</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Random structures &amp; algorithms</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Joos, Felix</au><au>Kim, Jaehoon</au><au>Kühn, Daniela</au><au>Osthus, Deryk</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Hypergraph regularity and random sampling</atitle><jtitle>Random structures &amp; algorithms</jtitle><date>2023-07</date><risdate>2023</risdate><volume>62</volume><issue>4</issue><spage>956</spage><epage>1015</epage><pages>956-1015</pages><issn>1042-9832</issn><eissn>1098-2418</eissn><abstract>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.</abstract><cop>New York</cop><pub>John Wiley &amp; Sons, Inc</pub><doi>10.1002/rsa.21126</doi><tpages>60</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1042-9832
ispartof Random structures & algorithms, 2023-07, Vol.62 (4), p.956-1015
issn 1042-9832
1098-2418
language eng
recordid cdi_proquest_journals_2817231573
source Wiley-Blackwell Read & Publish Collection
subjects Combinatorial analysis
Error analysis
Graph theory
hypergraph regularity
property testing
Random sampling
Regularity
Vertex sets
title Hypergraph regularity and random sampling
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-29T15%3A33%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Hypergraph%20regularity%20and%20random%20sampling&rft.jtitle=Random%20structures%20&%20algorithms&rft.au=Joos,%20Felix&rft.date=2023-07&rft.volume=62&rft.issue=4&rft.spage=956&rft.epage=1015&rft.pages=956-1015&rft.issn=1042-9832&rft.eissn=1098-2418&rft_id=info:doi/10.1002/rsa.21126&rft_dat=%3Cproquest_cross%3E2817231573%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c3326-36a6f8a15a68bd2346d8d50d70f6e725efd94122df036bbd535ddd74e983a6b43%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2817231573&rft_id=info:pmid/&rfr_iscdi=true