Szémeredi's regularity lemma and its applications in combinatorics
Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
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.
IdentifiersURN: urn:nbn:se:umu:diva-51333OAI: oai:DiVA.org:umu-51333DiVA: diva2:479100
UppsokPhysics, Chemistry, Mathematics
Häggkvist, Roland, Professor