Hypergraph regularity and random sampling

DOI10.1002/RSA.21126MaRDI QIDQ6076218zbMATH OpenOpenAlexFDO

Authors Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus

Publication date 23 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.01570

zbMATH Keywords

random samplingproperty testinghypergraph regularity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Randomized algorithms (68W20) Approximation algorithms (68W25) Hypergraphs (05C65)

Abstract: Suppose a $k$-uniform hypergraph $H$ that 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.

Recommendations

• On random sampling in uniform hypergraphs
• Hypergraph regularity and quasi-randomness
• Regularity lemmas for hypergraphs and quasi-randomness
• The counting lemma for regular k‐uniform hypergraphs
• Density and regularity theorems for semi-algebraic hypergraphs

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A tight bound for hypergraph regularity
• A variant of the hypergraph removal lemma
• An algorithmic hypergraph regularity lemma
• Efficient testing of large graphs
• Every Monotone Graph Property Is Testable
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Hypergraphs, quasi-randomness, and conditions for regularity
• On graphs with small subgraphs of large chromatic number
• On random sampling in uniform hypergraphs
• Property testing and its connection to learning and approximation
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Random sampling and approximation of MAX-CSPs
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Regularity Lemma for k-uniform hypergraphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testability and repair of hereditary hypergraph properties
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• The counting lemma for regular k‐uniform hypergraphs
• The uniformity lemma for hypergraphs
• Three theorems regarding testing graph properties
• Tight cycles and regular slices in dense hypergraphs

Cited in

(3)

• On random sampling in uniform hypergraphs
• Random hypergraph irregularity
• A characterization of testable hypergraph properties

This page was built for publication: Hypergraph regularity and random sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076218)