Paulovics Zoltán: "Általánosított Turán-tételek additív approximációja" (Noga Alon és Clara Shikhelman cikkei.)

Legyenek G, T gráfok, F pedig gráfok egy családja, ekkor jelölje
ex(G, T, F) a T-vel izomorf gráfok maximális számát a G azon részgráfjai
között, melyek nem tartalmaznak F-beli gráfot részgráfként.
(Persze ex(K_n, K_2, K_{p+1}) visszaadja a klasszikus Turán-problémát.)

Noga Alon és Clara Shikhelman "Additive Approximation of Generalized Turán
Questions" és "Many T copies in H-free graphs" cikkei alapján áttekintjük a
fontosabb eredményeket. Majd a Szemerédi regularitási lemma egy
algoritmikus változatát is használó, kis additív hibájú polinomiális
algoritmust adunk az ex(G, T, F) érték kiszámítására.