Hypergraph regularity and random sampling
From MaRDI portal
Publication:6076218
DOI10.1002/rsa.21126zbMath1525.05140arXiv2110.01570OpenAlexW3204950957MaRDI QIDQ6076218
Deryk Osthus, Felix Joos, Jae-Hoon Kim, Daniela Kühn
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
Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Approximation algorithms (68W25) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Tight cycles and regular slices in dense hypergraphs
- A variant of the hypergraph removal lemma
- On graphs with small subgraphs of large chromatic number
- The uniformity lemma for hypergraphs
- Hypergraphs, quasi-randomness, and conditions for regularity
- Random sampling and approximation of MAX-CSPs
- A tight bound for hypergraph regularity
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Testability and repair of hereditary hypergraph properties
- Property testing and its connection to learning and approximation
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Every Monotone Graph Property Is Testable
- Three theorems regarding testing graph properties
- An algorithmic hypergraph regularity lemma
- Regularity Lemma for k-uniform hypergraphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- On random sampling in uniform hypergraphs
- The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
- Regular Partitions of Hypergraphs: Regularity Lemmas
- The counting lemma for regular k‐uniform hypergraphs
- Efficient testing of large graphs
This page was built for publication: Hypergraph regularity and random sampling
