Turán-szám

A lap ellenőrzött változata (ellenőrizve: 2018. július 30.) ezen a változaton alapul.

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 (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.

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

(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: $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: $t(k,r)=\lim _{n\to \infty }{\frac {T(n,k,r)}{n \choose r}}$ , bár a $t(k,r)$ pontos értékét csak az r=2 esetben sikerült meghatározni.

További tények:

$t(k,r)\leq t(k-1,r-1)$ .
$T(n,k,r)\geq {\frac {n-k+1}{n-r+1}}{\frac {n \choose r}{k-1 \choose r-1}}$ .
$t(r+1,r)\leq {\frac {\ln r}{2r}}(1+o(1))$ .^[2]
$t(k,r)\leq \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.^[3]

Más kombinatorikai konstrukciókkal való kapcsolat

Megmutatható, hogy

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]

Kapcsolódó szócikkek

Fordítás

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.

Jegyzetek

↑ Katona Gyula, Nemetz Tibor, Simonovits Miklós, "Újabb bizonyítás a Turán-féle gráftételre és megjegyzések bizonyos általánosításaira", Mat. Lapok, 15 (1964) pp. 228–238
↑ A. Sidorenko, "Upper bounds on Turán numbers" J. Combin. Th. A , 77 : 1 (1997) pp. 134–147
↑ Colbourn & Dinitz 2007, pg. 649, Example 61.3
↑ Colbourn & Dinitz 2007, pg. 649, Remark 61.4
↑ Colbourn & Dinitz 2007, pg. 513, Proposition 32.12

Irodalom

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

[1] Katona Gyula, Nemetz Tibor, Simonovits Miklós, "Újabb bizonyítás a Turán-féle gráftételre és megjegyzések bizonyos általánosításaira", Mat. Lapok, 15 (1964) pp. 228–238

[2] A. Sidorenko, "Upper bounds on Turán numbers" J. Combin. Th. A , 77 : 1 (1997) pp. 134–147

[3] Colbourn & Dinitz 2007, pg. 649, Example 61.3

[4] Colbourn & Dinitz 2007, pg. 649, Remark 61.4

[5] Colbourn & Dinitz 2007, pg. 513, Proposition 32.12

[1]

[2]

[3]

[4]

[5]