Hypergraph regularity and random sampling

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 188
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorJoos, Felixko
dc.contributor.authorKim, Jaehoonko
dc.contributor.authorKuhn, Danielako
dc.contributor.authorOsthus, Derykko
dc.date.accessioned2023-06-07T07:00:15Z-
dc.date.available2023-06-07T07:00:15Z-
dc.date.created2023-03-27-
dc.date.created2023-03-27-
dc.date.issued2023-07-
dc.identifier.citationRANDOM STRUCTURES & ALGORITHMS, v.62, no.4, pp.956 - 1015-
dc.identifier.issn1042-9832-
dc.identifier.urihttp://hdl.handle.net/10203/307086-
dc.description.abstractSuppose 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.-
dc.languageEnglish-
dc.publisherWILEY-
dc.titleHypergraph regularity and random sampling-
dc.typeArticle-
dc.identifier.wosid000941093400001-
dc.identifier.scopusid2-s2.0-85149373447-
dc.type.rimsART-
dc.citation.volume62-
dc.citation.issue4-
dc.citation.beginningpage956-
dc.citation.endingpage1015-
dc.citation.publicationnameRANDOM STRUCTURES & ALGORITHMS-
dc.identifier.doi10.1002/rsa.21126-
dc.contributor.localauthorKim, Jaehoon-
dc.contributor.nonIdAuthorJoos, Felix-
dc.contributor.nonIdAuthorKuhn, Daniela-
dc.contributor.nonIdAuthorOsthus, Deryk-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorRandom sampling-
dc.subject.keywordAuthorhypergraph regularity-
dc.subject.keywordAuthorproperty testing-
dc.subject.keywordPlusGRAPH PROPERTIES-
dc.subject.keywordPlusLEMMA-
dc.subject.keywordPlusPROPERTY-
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0