Szemerédi’s Regularity Lemma and Its Applications;Szemerédi’s Regularity Lemma and Its Applications

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/74924

Title:	Szemerédi’s Regularity Lemma and Its Applications;Szemerédi’s Regularity Lemma and Its Applications
Authors:	譚芮妲;Tarigan, Regina Ayunita
Contributors:	數學系
Keywords:	extremal graph;partition graph;arithmetic progression;triangle removal lemma;graph density;random graphs;ϵ-regularity;ϵ-regular partition;equipartition;Szemerédi;Regularity Lemma;Roth′s Theorem;extremal graph;partition graph;arithmetic progression;triangle removal lemma;graph density;random graphs;ϵ-regularity;ϵ-regular partition;equipartition;Szemerédi;Regularity Lemma;Roth′s Theorem
Date:	2017-05-05
Issue Date:	2017-10-27 16:12:10 (UTC+8)
Publisher:	國立中央大學
Abstract:	在本篇論文中, 我們研讀探討在圖論領域裡的著名定理 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.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	347	View/Open

社群 sharing

Loading...