Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-51333OAI: oai:DiVA.org:umu-51333DiVA: diva2:479100
Uppsok
Physics, Chemistry, Mathematics
Examiners
Available from: 2012-03-01 Created: 2012-01-17 Last updated: 2012-03-23Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Mathematics and Mathematical Statistics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 808 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

urn-nbn

Altmetric score

urn-nbn
Total: 124 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf