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ó 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 határozta meg, a problémát általános r-re vetette fel. á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 Turán-szám az ilyen rendszer minimális méretét adja meg.
Eredmények áttekintése alapján az alábbi eredmények ismertek a Turán-számok problémakörében.
Rekurzív eredmény: .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
Ismert továbbá, hogy létezik a következő határérték: , bár a pontos értékét csak az r=2 esetben sikerült meghatározni.
További tények:
. .
.A. Sidorenko, "Upper bounds on Turán numbers" J. Combin. Th. A , 77 : 1 (1997) pp. 134–147 .
A kis , kis , valamint az 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
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
Jegyzetek
Irodalom
Godbole, A.P. (2001), "T/t120190", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer,
Kategória:Extremális gráfelmélet