Turán-szám

A matematika, a gráfelmélet, azon belül az extremális gráfelmélet területén egy n csúcsból álló, r-uniform hipergráfhoz tartozó $T(n,k,r)$ Turán-szám vagy Turán-féle szám megadja, hogy legalább hány r-élt kell tartalmaznia a hipergráfnak, hogy minden k csúcsú feszített részgráf tartalmazzon legalább egy élt közülük. A Turán-szám értékét r = 2-re Sablon:Harvtxt határozta meg, a problémát általános r-re Sablon:Harvtxt vetette fel. Sablon:Harv áttekintést ad a Turán-számokkal kapcsolatos összegyűlt tudásról.

Definíciók

Tekintsünk egy n csúcsból álló X halmazt. Adott r-re egy r-él vagy r-blokk egy r csúcsból álló halmaz. Blokkok egy halmazát Turán (n,k,r)-rendszernek (n ≥ k ≥ r) nevezzük, ha X minden k elemű részhalmaza tartalmaz blokkot. A $T(n,k,r)$ Turán-szám az ilyen rendszer minimális méretét adja meg.

Eredmények

Sablon:Harv áttekintése alapján az alábbi eredmények ismertek a Turán-számok problémakörében.

Rekurzív eredmény: $T(n,k,r)\ge \lceil \frac{n}{n-r}T(n-1,k,r)\rceil$.

Ismert továbbá, hogy létezik a következő határérték: $t(k,r)=\underset{n\to \mathrm{\infty }}{\lim }\frac{T(n,k,r)}{(\genfrac{}{}{0ex}{}{n}{r})}$, bár a $t(k,r)$ pontos értékét csak az r=2 esetben sikerült meghatározni.

További tények:

1. $t(k,r)\le t(k-1,r-1)$.
2. $T(n,k,r)\ge \frac{n-k+1}{n-r+1}\frac{(\genfrac{}{}{0ex}{}{n}{r})}{(\genfrac{}{}{0ex}{}{k-1}{r-1})}$.
3. $t(r+1,r)\le \frac{\ln r}{2r}(1+o(1))$.
4. $t(k,r)\le {\left(\frac{r-1}{k-1}\right)}^{r-1}$.

A kis $n/(k-1)$, kis $n-k$, valamint az $r=2,3,4$ eseteket már különböző szerzők részletesen tanulmányozták.

Példa

A Fano-sík egyeneseinek komplementerei Turán (7,5,4)-rendszert alkotnak. T(7,5,4) = 7.

Más kombinatorikai konstrukciókkal való kapcsolat

Megmutatható, hogy

$T(n,k,r)\ge (\genfrac{}{}{0ex}{}{n}{r}){(\genfrac{}{}{0ex}{}{k}{r})}^{-1}.$

Az egyenlőség pontosan akkor áll fenn, ha az S(n − k, n − r, n) Steiner-rendszer létezik.

Egy (n,r,k,r)-lottórendszer egy Turán (n, k, r)-rendszer. Ezért T(n,k, r) = L(n,r,k,r).

Kapcsolódó szócikkek

• Turán-típusú probléma
• Kombinatorikus rendszer

Fordítás

• Sablon:Fordítás

Jegyzetek

Irodalom

• Sablon:Citation
• Godbole, A.P. (2001), "T/t120190", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, Sablon:ISBN
• Sablon:Citation
• Sablon:Citation
• Sablon:Citation