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ó ${\displaystyle 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 (Turán 1941) határozta meg, a problémát általános r-re (Turán 1961) vetette fel. (Sidorenko 1995) áttekintést ad a Turán-számokkal kapcsolatos összegyűlt tudásról.

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 ${\displaystyle T(n,k,r)}$ Turán-szám az ilyen rendszer minimális méretét adja meg.

(Sidorenko 1995) áttekintése alapján az alábbi eredmények ismertek a Turán-számok problémakörében.

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

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

További tények:

1. ${\displaystyle t(k,r)\leq t(k-1,r-1)}$.
2. ${\displaystyle T(n,k,r)\geq {\frac {n-k+1}{n-r+1}}{\frac {n \choose r}{k-1 \choose r-1}}}$.
3. ${\displaystyle t(r+1,r)\leq {\frac {\ln r}{2r}}(1+o(1))}$.^[2]
4. ${\displaystyle t(k,r)\leq \left({\frac {r-1}{k-1}}\right)^{r-1}}$.

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

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

Megmutatható, hogy

${\displaystyle T(n,k,r)\geq {\binom {n}{r}}{\binom {k}{r}}^{-1}.}$

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

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).^[5]

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

• Ez a szócikk részben vagy egészben a Turán number című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• Colbourn, Charles J. & Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
• Godbole, A.P. (2001), "T/t120190", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
• Sidorenko, A. (1995), "What we know and what we do not know about Turán numbers", Graphs and Combinatorics 11 (2): 179–199, DOI 10.1007/BF01929486
• Turán, P (1941), "Egy gráfelméleti szélsőértékfeladatról (Hungarian. An extremal problem in graph theory.)", Mat. Fiz. Lapok 48: 436–452
• Turán, P. (1961), "Research problems", Magyar Tud. Akad. Mat. Kutató Int. Közl. 6: 417–423