Szemeredi's lemma for the analyst

被引：143

作者：

Lovasz, Laszlo

Szegedy, Balazs

机构：

[1] Eotvos Lorand Univ, Inst Math, H-1117 Budapest, Hungary

[2] Univ Toronto, Dept Math, Toronto, ON M5S 2E4, Canada

来源：

GEOMETRIC AND FUNCTIONAL ANALYSIS | 2007年 / 17卷 / 01期

关键词：

regularity lemma; cut norm; limits of graph sequences; compactness;

D O I：

10.1007/s00039-007-0599-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Szemeredi's regularity lemma is a fundamental tool in graph theory: it has many applications to extremal graph theory, graph property testing, combinatorial number theory, etc. The goal of this paper is to point out that Szemeredi's lemma can be thought of as a result in analysis. We show three different analytic interpretations.

引用

页码：252 / 270

页数：19

共 22 条

[1] A characterization of the (natural) graph properties testable with one-sided error [J].

Alon, N ;

Shapira, A .

46TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2005, :429-438

[2] Random sampling and approximation of MAX-CSPs [J].

Alon, N ;

de la Vega, WF ;

Kannan, R ;

Karpinski, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (02) :212-243

[3] Efficient testing of large graphs [J].

Alon, N ;

Fischer, E ;

Krivelevich, M ;

Szegedy, M .

COMBINATORICA, 2000, 20 (04) :451-476

[4]

ALON N, 1999, P 40 ANN S FDN COMP, P656

[5]

ALON N, 2005, P 37 ANN ACM S THEOR, P128

[6]

Alon Noga, 2004, Proc. of the 36th ACM STOC, P72, DOI 10.1145/1007352.1007371

[7]

BORGS C, UNPUB UNIQUE LIMITS

[8]

BORGS C, CONVERGENT SEQUENCES, V1

[9] Extremal problems on set systems [J].

Frankl, P ;

Rödl, V .

RANDOM STRUCTURES & ALGORITHMS, 2002, 20 (02) :131-164

[10] Quick approximation to matrices and applications [J].

Frieze, A ;

Kannan, R .

COMBINATORICA, 1999, 19 (02) :175-220

← 1 2 3 →