Change search
ReferencesLink to record
Permanent link

Direct link
What can Turán tell us about the hypercube?
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2012 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Vad kan Turán berätta för oss om hyperkuben? (Swedish)
Abstract [en]

The Turán problem is a fundamental problem in extremal graph theory. It asks what the maximum number of edges a given graph G can have, not containing some forbidden graph H, and is solved using the Turán number ex(n,H), density π(H) and graph Tr(n). Turán's theorem tells us that the Turán graph Tr(n) is the largest Kr+1-free simple graph on n vertices. This paper is an overview of Turán problems for cliques Kn, hypercubes Qn and Hamming graphs H(s,d). We end it by proving a new result we call "the layer theorem", solving the Hamming-Turán problem using a method of creating layers of vertices in a graph. This theorem gives a lower bound for the Hamming-relative Turán density as follows:  where  for the forbidden graph F stretching over t layers and r = χ(F).

Abstract [sv]

Turán-problemet är det fundamentala problemet inom extremal grafteori. Det ställer frågan vad det maximala antalet kanter en given graf G kan ha utan att innehålla någon förbjuden graf H, och löses med hjälp av Turán-talet ex(n,H), -densiteten π(H) and -grafen Tr(n). Turáns sats säger oss att Turán-grafen Tr(n) är den största Kr+1-fria enkla grafen på n hörn. Denna uppsats är en överblick av Turán-problem i klickar Kn, hyperkuber Qn och Hamming-grafer H(s,d). Vi avslutar den med att bevisa ett nytt resultat som vi kallar "lagersatsen", vilket löser Hamming-Turán-problemet med hjälp av en metod som skapar lager av hörnen i en graf. Lagersatsen ger en undre gräns för den Hamming-relativa Turán-densiteten enligt följande:  där  för den förbjudna grafen F som sträcker sig över t lager samt r = χ(F).

Place, publisher, year, edition, pages
2012. , 31 p.
Keyword [en]
Turán problem, graph theory, Turán's theorem, hypercube, Hamming graph, layer
Keyword [sv]
Turán-problem, grafteori, Turáns sats, hyperkub, Hamming-graf, lager
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-57789OAI: diva2:544732
Physics, Chemistry, Mathematics
Available from: 2012-10-31 Created: 2012-08-15 Last updated: 2012-10-31Bibliographically approved

Open Access in DiVA

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

Search in DiVA

By author/editor
Lantz, Emilott
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 285 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: 352 hits
ReferencesLink to record
Permanent link

Direct link