umu.sePublications
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
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
Identifiers
URN: urn:nbn:se:umu:diva-57789OAI: oai:DiVA.org:umu-57789DiVA: diva2:544732
Presentation
(Swedish)
Uppsok
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)339 downloads
File information
File name FULLTEXT01.pdfFile size 580 kBChecksum SHA-512
30cd3fff1646d7b97e535ddc51ed06d804b92c07ae515d52cfbab5cc04f99aaf77a3cdeb90840a17066249cf55a43ae17d4e7af9a232dcd2c52123d34fa73cbe
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: 339 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: 392 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