en>Nanite at 00:01, 21 January 2014

2014-01-21T00:01:41Z

← Older revision		Revision as of 02:01, 21 January 2014
Line 1:		Line 1:
	~~I am Latrice~~ and ~~was born~~ on 20 ~~December 1983~~. ~~My hobbies~~ are ~~Vintage clothing~~ and ~~Radio~~-~~Controlled Car Racing~~.<br><br>~~Here~~ is ~~my weblog~~ [http://~~Handmadeincolombia~~.~~com~~/?~~attachment_id~~=~~29 fifa 15 Coin generator~~]		In [[mathematics]], '''the [[Szemerédi]] regularity lemma''' states that every large enough [[graph (mathematics)\|graph]] can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. {{harvtxt\|Szemerédi\|1975}} introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove [[Szemerédi's theorem]], and in {{harv\|Szemerédi\|1978}} he proved the full lemma. Extensions of the regularity method to [[hypergraph]]s were obtained by [[Vojtěch Rödl\|Rödl]] and his collaborators<ref>P. Frankl, V. Rödl: Extremal problems on set systems, ''Random Structures & Algorithms'', '''20''' (2002), 131–164. {{doi\|10.1002/rsa.10017}}</ref><ref>V. Rödl, J. Skokan: Regularity lemma for uniform hypergraphs, ''Random Structures & Algorithms'', '''25''' (2004), 1–42. {{doi\|10.1002/rsa.20017}}</ref><ref>B. Nagle, V. Rödl, M. Schacht: The Counting Lemma for regular k-uniform hypergraphs, ''Random Structures & Algorithms'', '''28''' (2006), 113–179. {{doi\|10.1002/rsa.20117}}</ref> and [[Timothy Gowers\|Gowers]].<ref>W. T. Gowers: Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, ''Combinatorics, Probability and Computing'', '''15''' (2006), 143–184. {{doi\|10.1017/S0963548305007236}}</ref><ref>W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi theorem, ''Annals of Mathematics'', '''166''' (2007), 897–946. {{doi\|10.4007/annals.2007.166.897}}</ref>

			==Formal statement of the regularity lemma==
			The formal statement of Szemerédi's regularity [[lemma (mathematics)\|lemma]] requires some definitions. In what follows {{math\|''G''}} is a graph with [[vertex]] set {{math\|''V''}}.

			<blockquote>'''Definition 1.''' Let {{math\|''X'', ''Y''}} be disjoint subsets of {{math\|''V''}}. The '''density''' of the pair {{math\|(''X'', ''Y'')}} is defined as:

			:<math>d(X,Y) := \frac{\left\| E(X,Y) \right\|}{\|X\|\|Y\|}</math>

			where {{math\|''E''(''X'', ''Y'')}} denotes the set of edges having one end vertex in {{math\|''X''}} and one in {{math\|''Y''}}.</blockquote>

			<blockquote>'''Definition 2.''' For {{math\|ε > 0}}, a pair of vertex sets {{math\|''X''}} and {{math\|''Y''}} is called '''{{math\|ε}}-pseudo-random''', if for all subsets {{math\|''A'' ⊆ ''X''}}, {{math\|''B'' ⊆ ''Y''}} satisfying {{math\|<nowiki>\|</nowiki>''A''<nowiki>\|</nowiki> ≥ ε<nowiki>\|</nowiki>''X''<nowiki>\|</nowiki>}}, {{math\|<nowiki>\|</nowiki>''B''<nowiki>\|</nowiki> ≥ ε<nowiki>\|</nowiki>''Y''<nowiki>\|</nowiki>}}, we have

			:<math>\left\| d(X,Y) - d(A,B) \right\| \le \varepsilon.</math></blockquote>

			<blockquote>'''Definition 3.''' A partition of {{math\|''V''}} into {{math\|''k''}} sets: {{math\|''V''<sub>1</sub>, ...,  ''V<sub>k</sub>''}}, is called an '''{{math\|ε}}-regular partition''', if:
			*for all {{math\|''i'', ''j''}} we have: {{math\|<nowiki>\|</nowiki><nowiki>\|</nowiki>''V<sub>i</sub>''<nowiki>\|</nowiki> − <nowiki>\|</nowiki>''V<sub>j</sub>''<nowiki>\|</nowiki><nowiki>\|</nowiki> ≤ 1}};
			*all except {{math\|ε''k''<sup>2</sup>}} of the pairs {{math\|''V<sub>i</sub>''}}, {{math\|''V<sub>j</sub>''}}, {{math\|''i'' < ''j''}}, are {{math\|ε}}-pseudo-random.</blockquote>

			Now we can state the lemma:

			<blockquote>'''Regularity Lemma.''' For every {{math\|ε > 0}} and [[negative and positive numbers\|positive]] [[integer]] {{math\|''m''}} there exists an integer {{math\|''M''}} such that if {{math\|''G''}} is a graph with at least {{math\|''M''}} vertices, there exists an integer {{math\|''k''}} in the range {{math\|''m'' ≤ ''k'' ≤ ''M''}} and an {{math\|ε}}-regular partition of the vertex set of {{math\|''G''}} into {{math\|''k''}} sets.</blockquote>

			It is a common variant in the definition of an {{math\|ε}}-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set {{math\|''V''<sub>0</sub>}} whose size is at most an {{math\|ε}}-fraction of the size of the vertex set of {{math\|''G''}}.

			The bound {{math\|''M''}} for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a {{math\|ε<sup>−5</sup>}}-level iterated exponential of {{math\|''m''}}. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However {{harvtxt\|Gowers\|1997}} found examples of graphs for which {{math\|''M''}} does indeed grow very fast and is at least as large as a {{math\|ε<sup>−1/16</sup>}}-level iterated exponential of {{math\|''m''}}. In particular the best bound has level exactly 4 in the [[Grzegorczyk hierarchy]], and so is not an [[elementary recursive function]].

			== Extensions ==
			[[János Komlós (mathematician)\|János Komlós]], [[Gábor N. Sárközy\|Gábor Sárközy]] and [[Endre Szemerédi]] later proved in the [[blow-up lemma]]<ref>J. Komlós, G. N. Sárközy, E. Szemerédi: Blow-up Lemma, "Combinatorica", 17 (1), 1997, pp. 109-123. {{doi\|10.1007/BF01196135}}</ref><ref>J. Komlós, G. N. Sárközy, E. Szemerédi: An algorithmic version of the Blow-up Lemma, "Random Structures and Algorithms", 12, 1998, pp. 297-312. {{doi\|10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q}}</ref> that the regular pairs in Szemerédi regularity lemma behave like complete bipartite graphs under the correct conditions. The lemma allowed for deeper exploration into the nature of embeddings of large sparse graphs into dense graphs.

			==See also==
			* [[Algorithmic version for Szemerédi regularity partition]]

			==References==
			<references/>
			*{{Citation \| last1=Gowers \| first1=W. T. \| author1-link=Timothy Gowers \| title=Lower bounds of tower type for Szemerédi's uniformity lemma \| doi=10.1007/PL00001621 \| mr=1445389 \| year=1997 \| journal=Geometric and Functional Analysis \| volume=7 \| issue=2 \| pages=322–337}}
			* [[János Komlós (mathematician)\|Komlós, János]]; Miklos Simonovits: Szemerédi's regularity lemma and its applications in graph theory. Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295-352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
			*{{Citation \| last1=Komlós \| first1=János \| last2=Shokoufandeh \| first2=Ali \| last3=Simonovits \| first3=Miklós \| last4=Szemerédi \| first4=Endre \| author4-link=Endre Szemerédi \| title=Theoretical aspects of computer science (Tehran, 2000) \| publisher=[[Springer-Verlag]] \| location=Berlin, New York \| series=Lecture Notes in Comput. Sci. \| doi= 10.1007/3-540-45878-6_3 \| mr=1966181 \| year=2002 \| volume=2292 \| chapter=The regularity lemma and its applications in graph theory \| pages=84–112}}
			*{{Citation \| last1=Szemerédi \| first1=Endre \| author1-link=Endre Szemerédi \| title=On sets of integers containing no k elements in arithmetic progression \| url=http://matwbn.icm.edu.pl/tresc.php?wyd=6&tom=27 \| mr=0369312 \| year=1975 \| journal=Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica \| volume=27 \| pages=199–245}}
			*{{Citation \| last1=Szemerédi \| first1=Endre \| author1-link=Endre Szemerédi \| title=Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) \| publisher=CNRS \| location=Paris \| series=Colloq. Internat. CNRS \| mr=540024 \| year=1978 \| volume=260 \| chapter=Regular partitions of graphs \| pages=399–401}}

			{{DEFAULTSORT:Szemeredi regularity lemma}}
			[[Category:Graph theory]]
			[[Category:Lemmas]]

en>Bibcode Bot: Adding 0 arxiv eprint(s), 2 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot

2012-08-24T00:07:22Z

Adding 0 arxiv eprint(s), 2 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot

New page

I am Latrice and was born on 20 December 1983. My hobbies are Vintage clothing and Radio-Controlled Car Racing.<br><br>Here is my weblog [http://Handmadeincolombia.com/?attachment_id=29 fifa 15 Coin generator]

← Older revision		Revision as of 02:01, 21 January 2014
Line 1:		Line 1:
	~~I am Latrice~~ and ~~was born~~ on 20 ~~December 1983~~. ~~My hobbies~~ are ~~Vintage clothing~~ and ~~Radio~~-~~Controlled Car Racing~~.<br><br>~~Here~~ is ~~my weblog~~ [http://~~Handmadeincolombia~~.~~com~~/?~~attachment_id~~=~~29 fifa 15 Coin generator~~]		In [[mathematics]], '''the [[Szemerédi]] regularity lemma''' states that every large enough [[graph (mathematics)\|graph]] can be divided into subsets of about the same size so that the edges between different subsets behave almost randomly. {{harvtxt\|Szemerédi\|1975}} introduced a weaker version of this lemma, restricted to bipartite graphs, in order to prove [[Szemerédi's theorem]], and in {{harv\|Szemerédi\|1978}} he proved the full lemma. Extensions of the regularity method to [[hypergraph]]s were obtained by [[Vojtěch Rödl\|Rödl]] and his collaborators<ref>P. Frankl, V. Rödl: Extremal problems on set systems, ''Random Structures & Algorithms'', '''20''' (2002), 131–164. {{doi\|10.1002/rsa.10017}}</ref><ref>V. Rödl, J. Skokan: Regularity lemma for uniform hypergraphs, ''Random Structures & Algorithms'', '''25''' (2004), 1–42. {{doi\|10.1002/rsa.20017}}</ref><ref>B. Nagle, V. Rödl, M. Schacht: The Counting Lemma for regular k-uniform hypergraphs, ''Random Structures & Algorithms'', '''28''' (2006), 113–179. {{doi\|10.1002/rsa.20117}}</ref> and [[Timothy Gowers\|Gowers]].<ref>W. T. Gowers: Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, ''Combinatorics, Probability and Computing'', '''15''' (2006), 143–184. {{doi\|10.1017/S0963548305007236}}</ref><ref>W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi theorem, ''Annals of Mathematics'', '''166''' (2007), 897–946. {{doi\|10.4007/annals.2007.166.897}}</ref>

			==Formal statement of the regularity lemma==
			The formal statement of Szemerédi's regularity [[lemma (mathematics)\|lemma]] requires some definitions. In what follows {{math\|''G''}} is a graph with [[vertex]] set {{math\|''V''}}.

			<blockquote>'''Definition 1.''' Let {{math\|''X'', ''Y''}} be disjoint subsets of {{math\|''V''}}. The '''density''' of the pair {{math\|(''X'', ''Y'')}} is defined as:

			:<math>d(X,Y) := \frac{\left\| E(X,Y) \right\|}{\|X\|\|Y\|}</math>

			where {{math\|''E''(''X'', ''Y'')}} denotes the set of edges having one end vertex in {{math\|''X''}} and one in {{math\|''Y''}}.</blockquote>

			<blockquote>'''Definition 2.''' For {{math\|ε > 0}}, a pair of vertex sets {{math\|''X''}} and {{math\|''Y''}} is called '''{{math\|ε}}-pseudo-random''', if for all subsets {{math\|''A'' ⊆ ''X''}}, {{math\|''B'' ⊆ ''Y''}} satisfying {{math\|<nowiki>\|</nowiki>''A''<nowiki>\|</nowiki> ≥ ε<nowiki>\|</nowiki>''X''<nowiki>\|</nowiki>}}, {{math\|<nowiki>\|</nowiki>''B''<nowiki>\|</nowiki> ≥ ε<nowiki>\|</nowiki>''Y''<nowiki>\|</nowiki>}}, we have

			:<math>\left\| d(X,Y) - d(A,B) \right\| \le \varepsilon.</math></blockquote>

			<blockquote>'''Definition 3.''' A partition of {{math\|''V''}} into {{math\|''k''}} sets: {{math\|''V''<sub>1</sub>, ...,  ''V<sub>k</sub>''}}, is called an '''{{math\|ε}}-regular partition''', if:
			*for all {{math\|''i'', ''j''}} we have: {{math\|<nowiki>\|</nowiki><nowiki>\|</nowiki>''V<sub>i</sub>''<nowiki>\|</nowiki> − <nowiki>\|</nowiki>''V<sub>j</sub>''<nowiki>\|</nowiki><nowiki>\|</nowiki> ≤ 1}};
			*all except {{math\|ε''k''<sup>2</sup>}} of the pairs {{math\|''V<sub>i</sub>''}}, {{math\|''V<sub>j</sub>''}}, {{math\|''i'' < ''j''}}, are {{math\|ε}}-pseudo-random.</blockquote>

			Now we can state the lemma:

			<blockquote>'''Regularity Lemma.''' For every {{math\|ε > 0}} and [[negative and positive numbers\|positive]] [[integer]] {{math\|''m''}} there exists an integer {{math\|''M''}} such that if {{math\|''G''}} is a graph with at least {{math\|''M''}} vertices, there exists an integer {{math\|''k''}} in the range {{math\|''m'' ≤ ''k'' ≤ ''M''}} and an {{math\|ε}}-regular partition of the vertex set of {{math\|''G''}} into {{math\|''k''}} sets.</blockquote>

			It is a common variant in the definition of an {{math\|ε}}-regular partition to require that the vertex sets all have the same size, while collecting the leftover vertices in an "error"-set {{math\|''V''<sub>0</sub>}} whose size is at most an {{math\|ε}}-fraction of the size of the vertex set of {{math\|''G''}}.

			The bound {{math\|''M''}} for the number of parts in the partition of the graph given by the proofs of Szemeredi's regularity lemma is very large, given by a {{math\|ε<sup>−5</sup>}}-level iterated exponential of {{math\|''m''}}. At one time it was hoped that the true bound was much smaller, which would have had several useful applications. However {{harvtxt\|Gowers\|1997}} found examples of graphs for which {{math\|''M''}} does indeed grow very fast and is at least as large as a {{math\|ε<sup>−1/16</sup>}}-level iterated exponential of {{math\|''m''}}. In particular the best bound has level exactly 4 in the [[Grzegorczyk hierarchy]], and so is not an [[elementary recursive function]].

			== Extensions ==
			[[János Komlós (mathematician)\|János Komlós]], [[Gábor N. Sárközy\|Gábor Sárközy]] and [[Endre Szemerédi]] later proved in the [[blow-up lemma]]<ref>J. Komlós, G. N. Sárközy, E. Szemerédi: Blow-up Lemma, "Combinatorica", 17 (1), 1997, pp. 109-123. {{doi\|10.1007/BF01196135}}</ref><ref>J. Komlós, G. N. Sárközy, E. Szemerédi: An algorithmic version of the Blow-up Lemma, "Random Structures and Algorithms", 12, 1998, pp. 297-312. {{doi\|10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.0.CO;2-Q}}</ref> that the regular pairs in Szemerédi regularity lemma behave like complete bipartite graphs under the correct conditions. The lemma allowed for deeper exploration into the nature of embeddings of large sparse graphs into dense graphs.

			==See also==
			* [[Algorithmic version for Szemerédi regularity partition]]

			==References==
			<references/>
			*{{Citation \| last1=Gowers \| first1=W. T. \| author1-link=Timothy Gowers \| title=Lower bounds of tower type for Szemerédi's uniformity lemma \| doi=10.1007/PL00001621 \| mr=1445389 \| year=1997 \| journal=Geometric and Functional Analysis \| volume=7 \| issue=2 \| pages=322–337}}
			* [[János Komlós (mathematician)\|Komlós, János]]; Miklos Simonovits: Szemerédi's regularity lemma and its applications in graph theory. Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295-352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
			*{{Citation \| last1=Komlós \| first1=János \| last2=Shokoufandeh \| first2=Ali \| last3=Simonovits \| first3=Miklós \| last4=Szemerédi \| first4=Endre \| author4-link=Endre Szemerédi \| title=Theoretical aspects of computer science (Tehran, 2000) \| publisher=[[Springer-Verlag]] \| location=Berlin, New York \| series=Lecture Notes in Comput. Sci. \| doi= 10.1007/3-540-45878-6_3 \| mr=1966181 \| year=2002 \| volume=2292 \| chapter=The regularity lemma and its applications in graph theory \| pages=84–112}}
			*{{Citation \| last1=Szemerédi \| first1=Endre \| author1-link=Endre Szemerédi \| title=On sets of integers containing no k elements in arithmetic progression \| url=http://matwbn.icm.edu.pl/tresc.php?wyd=6&tom=27 \| mr=0369312 \| year=1975 \| journal=Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica \| volume=27 \| pages=199–245}}
			*{{Citation \| last1=Szemerédi \| first1=Endre \| author1-link=Endre Szemerédi \| title=Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) \| publisher=CNRS \| location=Paris \| series=Colloq. Internat. CNRS \| mr=540024 \| year=1978 \| volume=260 \| chapter=Regular partitions of graphs \| pages=399–401}}

			{{DEFAULTSORT:Szemeredi regularity lemma}}
			[[Category:Graph theory]]
			[[Category:Lemmas]]

Scanning tunneling spectroscopy - Revision history

en>Nanite at 00:01, 21 January 2014

en>Bibcode Bot: Adding 0 arxiv eprint(s), 2 bibcode(s) and 0 doi(s). Did it miss something? Report bugs, errors, and suggestions at User talk:Bibcode Bot