Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-05T21:41:13.634Z Has data issue: false hasContentIssue false
  • English
  • Français

On Regularity Lemmas and their Algorithmic Applications

Published online by Cambridge University Press:  28 March 2017

JACOB FOX ,
LÁSZLÓ MIKLÓS LOVÁSZ  and
YUFEI ZHAO
JACOB FOX
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: [email protected])
LÁSZLÓ MIKLÓS LOVÁSZ
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail: [email protected])
YUFEI ZHAO
Affiliation:
Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Szemerédi'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 ε′>ε, an ε′-regular partition with k parts if there exists an ε-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.

Keywords

Primary 05C85Secondary 05C5005D99
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 4 , July 2017 , pp. 481 - 505
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N., Duke, R. A., Lefmann, H., Rödl, V. and Yuster, R. (1994) The algorithmic aspects of the regularity lemma. J. Algorithms 16 80–109.Google Scholar
[2] Alon, N. and Naor, A. (2006) Approximating the cut-norm via Grothendieck's inequality. SIAM J. Comput. 35 787–803.Google Scholar
[3] Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley.Google Scholar
[4] Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T. and Vesztergombi, K. (2008) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219 1801–1851.Google Scholar
[5] Conlon, D. and Fox, J. (2012) Bounds for graph regularity and removal lemmas. Geom. Funct. Anal. 22 1191–1256.Google Scholar
[6] Cooper, J. N. (2006) A permutation regularity lemma. Electron. J. Combin. 13 22.Google Scholar
[7] Coppersmith, D. and Winograd, S. (1990) Matrix multiplication via arithmetic progressions. J. Symbol. Comput. 9 251–280.Google Scholar
[8] Dellamonica, D., Kalyanasundaram, S., Martin, D., Rödl, V. and Shapira, A. (2012) A deterministic algorithm for the Frieze–Kannan regularity lemma. SIAM J. Discrete Math. 26 15–29.Google Scholar
[9] Dellamonica, D. Jr, Kalyanasundaram, S., Martin, D. M., Rödl, V. and Shapira, A. (2015) An optimal algorithm for finding Frieze–Kannan regular partitions. Combin. Probab. Comput. 24 407–437.Google Scholar
[10] Duke, R. A., Lefmann, H. and Rödl, V. (1995) A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM J. Comput. 24 598–620.Google Scholar
[11] Fischer, E., Matsliah, A. and Shapira, A. (2010) Approximate hypergraph partitioning and applications. SIAM J. Comput. 39 3155–3185.Google Scholar
[12] Fox, J. and Lovász, L. M. A tight lower bound for Szemerédi's regularity lemma. Combinatorica, to appear.Google Scholar
[13] Frieze, A. and Kannan, R. (1999) Quick approximation to matrices and applications. Combinatorica 19 175–220.Google Scholar
[14] Frieze, A. and Kannan, R. (1999) A simple algorithm for constructing Szemerédi's regularity partition. Electron. J. Combin. 6 17.Google Scholar
[15] Gowers, W. T. (1997) Lower bounds of tower type for Szemerédi's uniformity lemma. Geom. Funct. Anal. 7 322–337.Google Scholar
[16] Håstad, J. (1999) Clique is hard to approximate within n 1-ε . Acta Mathematica 182 105–142.Google Scholar
[17] Hoppen, C., Kohayakawa, Y. and Sampaio, R. M. (2012) A note on permutation regularity. Discrete Appl. Math. 160 2716–2727.Google Scholar
[18] Kohayakawa, Y., Rödl, V. and Thoma, L. (2003) An optimal algorithm for checking regularity. SIAM J. Comput. 32 1210–1235.Google Scholar
[19] Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty, Vol. 2, János Bolyai Mathematical Society, pp. 295–352.Google Scholar
[20] Le Gall, F. (2014) Powers of tensors and fast matrix multiplication. In ISSAC '14: Proc. 39th International Symposium on Symbolic and Algebraic Computation, ACM, pp. 296–303.Google Scholar
[21] Lovász, L. (2012) Large Networks and Graph Limits, Vol. 60 of American Mathematical Society Colloquium Publications, AMS.Google Scholar
[22] Lovász, L. and Szegedy, B. (2007) Szemerédi's lemma for the analyst. Geom. Funct. Anal. 17 252–270.CrossRefGoogle Scholar
[23] Moshkovitz, G. and Shapira, A. (2016) A short proof of Gowers' lower bound for the regularity lemma. Combinatorica 36 187–194.Google Scholar
[24] Szemerédi, E. (1975) On sets of integers containing no k elements in arithmetic progression. In Proc. International Congress of Mathematicians 1974, Vol. 2, Canadian Mathematical Congress, pp. 503–505.Google Scholar
[25] Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, Vol. 260 of Colloq. Internat. CNRS, CNRS, pp. 399–401.Google Scholar
[26] Tao, T. (2010) An Epsilon of Room, II, AMS.Google Scholar
[27] Zuckerman, D. (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3 103–128.Google Scholar