Change search
ReferencesLink to record
Permanent link

Direct link
Szémeredi's regularity lemma and its applications in combinatorics
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2006 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Szemerédi’s regularity lemma is a deep result in graph theory with applications in many different areas of mathematics. The lemma says that any graph can be approximated by the union of a bounded num- ber of random-like bipartite graphs and this can be used to extract the underlying structure of the graph. Recently it has been shown that there exists polynomial time algorithms that can make this ap- proximation. This survey gives a proof of the regularity lemma, shows some applications and discusses some algorithmic aspects. 

Place, publisher, year, edition, pages
2006. , 49 p.
National Category
URN: urn:nbn:se:umu:diva-51333OAI: diva2:479100
Physics, Chemistry, Mathematics
Available from: 2012-03-01 Created: 2012-01-17 Last updated: 2012-03-23Bibliographically approved

Open Access in DiVA

fulltext(322 kB)691 downloads
File information
File name FULLTEXT01.pdfFile size 322 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics and Mathematical Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 691 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 98 hits
ReferencesLink to record
Permanent link

Direct link