Change search

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: $\pi_{s,d}(\mathcal{H}_{s,d},F) \geq 1 - \dfrac{f+g}{||H(s,d)||}$ where $f = \binom{s}{2}\left(1-\dfrac{r-2}{r-1}\right)ds^{d-1} \text{ and } g = \sum_{i=1}^{n/(t-1)} (d-i(t-1))(s-1)^{i(t-1)+1}\binom{d}{i(t-1)}$ 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: $\pi_{s,d}(\mathcal{H}_{s,d},F) \geq 1 - \dfrac{f+g}{||H(s,d)||}$ där $f = \binom{s}{2}\left(1-\dfrac{r-2}{r-1}\right)ds^{d-1} \text{ and } g = \sum_{i=1}^{n/(t-1)} (d-i(t-1))(s-1)^{i(t-1)+1}\binom{d}{i(t-1)}$ för den förbjudna grafen F som sträcker sig över t lager samt r = χ(F).

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
OAI: oai:DiVA.org:umu-57789DiVA: diva2:544732
(Swedish)
##### Uppsok
Physics, Chemistry, Mathematics
Available from: 2012-10-31 Created: 2012-08-15 Last updated: 2012-10-31Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 580 kBChecksum SHA-512
30cd3fff1646d7b97e535ddc51ed06d804b92c07ae515d52cfbab5cc04f99aaf77a3cdeb90840a17066249cf55a43ae17d4e7af9a232dcd2c52123d34fa73cbe
Type fulltextMimetype application/pdf

#### Search in DiVA

Lantz, Emilott
##### By organisation
Department of Mathematics and Mathematical Statistics
##### On the subject
Discrete Mathematics

#### Search outside of DiVA

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

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
v. 2.29.1
|