Szemerédi’s Regularity Lemma and Its Applications

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：18.191.157.191

姓名

譚芮妲(Regina Ayunita Tarigan) 查詢紙本館藏

畢業系所

數學系

論文名稱

Szemerédi’s Regularity Lemma and Its Applications
(Szemerédi’s Regularity Lemma and Its Applications)

相關論文

★ 加乘法估計在實數體中一些變化的探討	★ 傅氏分析在組合學的應用與Roth定理
★ 機率方法再組合學中的探討	★ 歐氏空間富式分析的探討
★ 加減法集合的估計以及其運用	★ 洛倫茲空間及其對偶空間

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在本篇論文中, 我們研讀探討在圖論領域裡的著名定理 Szemerédi’s Regularity Lemma 以及此定理的應用. 簡單來說 Szemerédi’s Regularity Lemma 可以將一個圖分解成許多幾乎相等的分割, 而這些分割之間彼此兩兩幾乎是隨機的分佈. 最後我們將討論如何使用此定理運用在數論的一個著名的定理, 所謂的 Roth′s Theorem. 此定理敘述任一個整數的子集合存在長度為三的等差數列只要此集合的密度大於零.

摘要(英)

In this dissertation, the Szemerédi’s Regularity Lemma and its application are studied. This lemma is used to partition a large enough graph into almost equal parts so that the number of edges across the parts is fairly random. On the other hand, Roth′s Theorem states that there exists an arithmetic progression with length 3 in a subset in integer with positive upper density. We shall see that it can be proved by using triangle removal lemma, which is an application of Szemerédi’s Regularity Lemma.

關鍵字(中)

★ extremal graph
★ partition graph
★ arithmetic progression
★ triangle removal lemma
★ graph density
★ random graphs
★ ϵ-regularity
★ ϵ-regular partition
★ equipartition
★ Szemerédi
★ Regularity Lemma
★ Roth′s Theorem

關鍵字(英)

論文目次

摘要 i
Abstract ii
Acknowledgementiii
Contentsiv
List of Figuresv
1 Introduction 1
1.1 A Brief Overview of GraphTheory............1
1.2 Some Necessary Terms...................3
1.3 The Degree of a Vertex...................5
1.4 Bipartite Graph.......................6
1.5 Clique and Independent Set................7
2 Extremal GraphTheory 8
2.1 Forbidden Subgraph Problem...............8
2.2 Complete Subgraph.....................8
2.3 Turán Graph (Tr(n)) ....................8
2.4 Erdös-Stone Theorem....................10
3 Szemerédi’s Regularity Lemma 11
3.1 Brief Overview.......................11
3.2 Szemerédi′s Regularity Lemma...............13
4 Further Concept and Application of Szemerédi′s Regu-
larity Lemma 21
4.1 Some Historical Background................21
4.2 Extremal Problem.....................22
4.3 Removal Lemma......................24
4.4 Roth′s Theorem in Arithmetic Progression (k = 3)....28
References 30

參考文獻

[1] Bella Bollobas. Modern Graph Theory. Springer-Verlag,New York,2005.
[2] Reinhart Diestel. GraphTheory. Springer-Verlag,New York,1998.
[3] C.L.Liu Introduction to Combinatorial Mathematics. McGraw-Hill,USA, 1968.
[4] Debidash Gosh. Introduction to Theory of Automata,Formal Languages, and Computation (Ebook version). PHI Learning Private Limited, Delhi,2013.
[5] Bela Bollobas. Extremal Graph Theory. Academic Press Inc., New York,1978.
[6] Bruce.M. Landman and Aaron Robertson. Ramsey Theory on the
Integers. American Mathematical Society,USA,2014.
[7] Chongbumm Lee.Lecture Notes: Lecture 3. Regularity Lemma.
MIT, Massachusetts,2015.
[8] Fan Chung Graham. Lecture Notes: The Combinatorics of Pat-
terns in Subsets and Graphs. University of California San Diego,San Diego,2004.
[9] Brandon Hanson.Student Papers: Analysis in Graph Theory and
Szemerédi′s Regularity Lemma. Wiki of the Department of Mathe-
matics ofthe University of Toronto,2010.
[10] Shagnik Das.Notes: Applications of the Szemerédi′s Regularity Lemma. Wiki of the Department of Mathematics of the University of Toronto,2010.
[11] Cassie Deskus.Student Papers: An Introduction to the Regularity Lemma. University of Chicago,2011.
[12] Jonas Hägglund. Master Thesis: Szemerédi′s regularity lemma and its applications in combinatorics. Umeå University, Sweden,2006.
[13] Anna Llado.International Workshop Materials: CIMPA-
UNESCO-INDONESIA School on Extremal Problems and Hamiltonicity in Graphs: An Introduction to Extremal Graph Theory.
ITB, Indonesia,2009.
[14] Endre Szemeredi, On the sets of integers containing no k
elements in arithmetic progression, Polska Akademia Nauk.Instytut Matematyczny. ActaArithmetica, 27 (1975), 199-245.30
[15] Endre Szemerédi, Regular partitions of graphs (French summary) Problèm es combinatoire set theorié des graphes, Colloq.Internat. CNRS, 260, CNRS,Paris 260 (1978), 399-401.
[16] B.L.van der Waerden, Beweis einer Baudetschen Vermutung.
(German version),Nieuw Archief voor Wiskunde.Tweede Serie, 15
(1927), 212-216.
[17] Paul Erdös and Paul Turán, On some sequences of integers, Journal of the London Mathematical Society, 11(4) (1936),261-264.
[18] Klaus Friedrich Roth, On certain sets of integers, Journalofthe London Mathematical Society, 28(1) (1953),104-109.
[19] Endre Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad.Sci.Hung, 20 (1969),89-104.
[20] János Komlós, Ali Shokoufandeh, Miklós Simonovits,and Endre Szemerédi, The Regularity Lemma and Its Applications in Graph Theory,G.B. Khosrovshahietal.(Eds.):Theoretical Aspects of Computer Science, LNCS 2292 (2002), 84-112.
[21] Wikipedia:Handshaking lemma,
https://en.wikipedia.org/wiki/Handshaking lemma.
[22] Wikipedia:Bipartite graph,
https://en.wikipedia.org/wiki/Bipartite graph.
[23] WolframMathworld:Complete Bipartite Graph,
http://mathworld.wolfram.com/CompleteBipartiteGraph.html.
[24] Wikipedia:Clique,
https://en.wikipedia.org/wiki/Clique (graph theory).
[25] Wikipedia:Independent set (graph theory),
https://en.wikipedia.org/wiki/Independent set (graph theory).
[26] Wikipedia:Turán′s Theorem,
https://en.wikipedia.org/wiki/Turán′s theorem
[27] Wikipedia:Extremal graph theory,
https://en.wikipedia.org/wiki/Extremal graph theory.
[28] Disquisitiones Mathematicae: Applications of Szemerédi′s regularity lemma: triangle removal lemma, Roth′stheorem, Corner′s theorem and graph removal lemma,
https://matheuscmss.wordpress.com/2012/01/07/applications
-of-szemeredis-regularity-lemma-triangle-removal-lemma
-roths-theorem-corners-theorem-and-graph-removal-lemma/.

指導教授

沈俊嚴(Chun-Yen Shen)

審核日期

2017-5-5

推文