On regularity lemmas and their algorithmic applications

DOI10.1017/S0963548317000049MaRDI QIDQ5366957zbMATH OpenOpenAlexWikidataFDO

Authors Jacob Fox, László Miklós Lovász, Yufei Zhao

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Szemerédi's regularity lemmaweak Frieze-Kannan regularity lemma

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Extremal combinatorics (05D99)

Abstract: Szemer'edi's regularity lemma and its variants are some of the most powerful tools in combinatorics. In this paper, we establish several results around the regularity lemma. First, we prove that whether or not we include the condition that the desired vertex partition in the regularity lemma is equitable has a minimal effect on the number of parts of the partition. Second, we use an algorithmic version of the (weak) Frieze--Kannan regularity lemma to give a substantially faster deterministic approximation algorithm for counting subgraphs in a graph. Previously, only an exponential dependence for the running time on the error parameter was known, and we improve it to a polynomial dependence. Third, we revisit the problem of finding an algorithmic regularity lemma, giving approximation algorithms for several co-NP-complete problems. We show how to use the weak Frieze--Kannan regularity lemma to approximate the regularity of a pair of vertex subsets. We also show how to quickly find, for each $epsilo{n}^{\prime }>epsilon$, an $epsilo{n}^{\prime }$-regular partition with $k$ parts if there exists an $epsilon$-regular partition with $k$ parts. Finally, we give a simple proof of the permutation regularity lemma which improves the tower-type bound on the number of parts in the previous proofs to a single exponential bound.

Recommendations

• scientific article; zbMATH DE number 1512671
• The Algorithmic Aspects of the Regularity Lemma
• Approximate hypergraph partitioning and applications
• scientific article; zbMATH DE number 1256685
• A deterministic algorithm for the Frieze-Kannan regularity lemma

Cites work

• A deterministic algorithm for the Frieze-Kannan regularity lemma
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• A note on permutation regularity
• A permutation regularity lemma
• A short proof of Gowers' lower bound for the regularity lemma
• A simple algorithm for constructing Szemerédi's regularity partition
• A tight lower bound for Szemerédi's regularity lemma
• An epsilon of room. I: Real analysis. Pages from year three of a mathematical blog
• An Optimal Algorithm for Checking Regularity
• An optimal algorithm for finding Frieze-Kannan regular partitions
• Approximate hypergraph partitioning and applications
• Approximating the Cut-Norm via Grothendieck's Inequality
• Bounds for graph regularity and removal lemmas
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• scientific article; zbMATH DE number 3523693 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Large networks and graph limits
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Matrix multiplication via arithmetic progressions
• Powers of tensors and fast matrix multiplication
• Quick approximation to matrices and applications
• Szemerédi's lemma for the analyst
• The Algorithmic Aspects of the Regularity Lemma
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(26)

• Lepp-bisection algorithms, applications and mathematical properties
• Limitations on regularity lemmas for clustering graphs
• Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Regularity lemmas and combinatorial algorithms
• Regularity lemmas for graphs
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Fast property testing and metrics for permutations
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• An Algorithmic Version of the Hypergraph Regularity Method
• Can a Graph Have Distinct Regular Partitions?
• scientific article; zbMATH DE number 1256685 (Why is no real title available?)
• The Algorithmic Aspects of the Regularity Lemma
• scientific article; zbMATH DE number 1512671 (Why is no real title available?)
• A sparse regular approximation lemma
• scientific article; zbMATH DE number 2086426 (Why is no real title available?)
• scientific article; zbMATH DE number 2119673 (Why is no real title available?)
• Erratum to: ``On regularity lemmas and their algorithmic applications
• Estimating parameters associated with monotone properties
• Amplification and Derandomization without Slowdown
• Regularity Lemmas and Combinatorial Algorithms
• A fast new algorithm for weak graph regularity
• Approximate hypergraph partitioning and applications
• A note on permutation regularity
• Efficient polynomial-time approximation scheme for the genus of dense graphs
• A permutation regularity lemma

This page was built for publication: On regularity lemmas and their algorithmic applications

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