A kombinatorika (amit itt tágabb értelemben, többé-kevésbé a „véges matematika” vagy „diszkrét matematika” szinonímájaként értünk), évszázadokig a matematika határán vegetált. A 20. század második felében azonban már a matematika egyik leggyorsabban növekvő ága lett – különösen, ha alkalmazásainak széles skáláját tekintjük a természettudományokban (statisztikus fizika), közgazdaságtanban (operációkutatás), a mérnöki tudományokban és (legfőképpen) a számítástudományban.
A matematika világa évszázadok óta az algebra és analízis sikereinek bűvöletében él. Csak a 20. század második felében vált világossá, főleg a fent említett alkalmazások kapcsán, hogy a kombinatorika, a véges halmazok és struktúrák tudománya a korábbiaktól különböző problémákat vet fel, és új módszereket kínál ezek megoldására. Ezek különböznek az algebra és analízis problémáitól, de vetekszenek azokkal nehézségben, elméleti és gyakorlati érdekességben, és szépségben.
Sok kiváló matematikus kombinatorikáról alkotott véleménye azonban hosszú ideig nem volt hízelgő. Elfogadták ugyan, hogy érdekes, hasznos és talán szép is, de megkérdőjelezték mélységét. Kifogásolták, hogy a kombinatorika különálló problémák gyüjteménye, melyek önmagukban érdekesek, de nem állnak össze elméletté. Könnyű új eredményeket elérni, mert – úgymond – kevés technikát kell megtanulni, és ez túl sok publikációhoz vezet.
Könyvem első, angol nyelvű kiadásának előszavában (mely 1979-ben jelent meg) amellett érveltem, hogy ezek a hiányosságai minden olyan tudományos területnek megvannak, mely fejlődésének korai szakaszában van, amit adatgyűjtési szakasznak nevezhetünk. Amíg a fő kérdések nincsenek megfogalmazva, a kellően általános szintű absztrakciók nincsenek megalkotva, addig nehéz megmondani, hogy egy-egy eredmény mennyire érdekes – kivéve esztétikai alapon, ami természetesen igen szubjektív. De ha elfogadjuk, hogy a terület fontos (és az alkalmazásokon kívül a matematika belső logikája is ezt támasztja alá), akkor ezek a fő kérdések, absztrakciók, paradigmák megfogalmazójukra várnak. Így nem, hogy eltanácsolni kell a fiatal tudósokat erről a területről, hanem ellenkezőleg, rámutatni a lehetőségeire.
Az első kiadás óta a kombinatorikáról alkotott kép sokat módosult világszerte. A kombinatorikán belül egyre több olyan tételsor, részterület jött létre, mely mélységben felér a klasszikus matematika elméleteivel (ilyen a matroidelmélet, vagy a gráf-minorok Robertson–Seymour-féle elmélete). Számos komoly technika alakult ki, melyek doktori kurzusok anyagát alkotják (valószinűségszámítási módszer, lineáris algebrai és topológiai módszerek, poliéderes kombinatorika, stb.) Ma már nehéz, talán lehetetlen fontos kombinatorikai eredményt elérni az ilyen módszerek alkalmazása nélkül.
* * * |
Még egyetemista voltam, amikor Rábai Imre tanár úr, középiskolai matematika tanárom arra bíztatott, hogy állítsak össze egy feladatgyűjteményt kombinatorikából. Lelkesen vágtam bele a dologba. ő középiskolai szintű feladatgyűjteményre gondolt, de engem magával sodort a feladat. A „Pólya–Szegő”, a klasszikus analízis bibliája (Aufgaben und Lehrsätze aus der Analysis, Springer, 1925) lebegett a szemem előtt. Mai eszemmel röstellem az összehasonlítást, hiszen sem a felkészültségem nem volt az övekéhez mérhető, sem a téma nem volt olyan nagy, homogén, és jól definált, mint az övék. De a feldatgyűjtemény műfaja így is jónak bizonyult, és a könyvből magam is, mások is tanítani tudtak.
Amikor néhány éve a könyv második (angol nyelvű) kiadásának szerkesztői megkértek, hogy javitsam és bővítsem ki az eredetit, el kellett határoznom, mennyit akarok rajta változtatni. Figyelembe kellett vennem, hogy milyen sokat fejlődött a terület, de azt is, hogy az első kiadás elfogyott, és szerették volna minnél hamarabb újranyomni. A kombinatorika igen megnőtt időközben, főleg az olyan területeken, melyek a matematika más ágaival voltak kölcsönhatásban, mint például a poliéderes kombinatorika, algebrai kombinatorika, kombinatorikus geometria, véletlen struktúrák, és legfőképpen, algoritmikus kombinatorika és bonyolultságelmélet. (A számításelméletnek olyan sok alkalmazása van a kombinatorikában, és megfordítva, hogy gyakran nehéz meghúzni közöttük a határt.)
De a kombinatorika mégiscsak különálló diszciplina, és így végül is úgy döntöttem, hogy a feladatgyűjtemény (némi felújítás után) még mindíg megáll a lábán. Nem változtattam meg a könyv struktúráját és fő témáit; koncepcionális vátoztatáshoz (mondjuk, az algoritmikus szemlélet következetes végigviteléhez, beleértve az algoritmusok analízisét és az algoritmikus problémák bonyolultságelméleti klasszifikációját) új könyvet kellett volna írni. De annak nem tudtam ellenállni, hogy kidolgozzak egy feladatsort, mely a gráfokon való bolyongásokat (véletlen sétákat), és ezeknek a sajátértékekkel és elektromos hálózatok ellenállásával való kapcsolatát tárgyalja. (Ez a terület a klasszikus matematikában gyökerezik, de az utóbbi évtizedben viharosan fejlődött.) Így a 11. fejezet sokkal hosszabb lett. Több más fejezetben is kidolgoztam új problémákat, átirtam néhány régit, és egyszerűsítettem megoldásokat.
A mostani magyar kiadás ennek a második angol nyelvű kiadásnak a fordítása. Természetesen kijavítottam számos elírást, képlethibát, ami a fordítás során előkerült.
Már az első kiadásban is, de később persze még inkább korlátozni kellett a témákat. Jobbnak látszott kevesebb téma alapos körüljárása, mint sok téma felületes érintése. Így végülis a leszámlálások elmélete, a gráfelmélet és a halmazrendszerek (hipergráfok) elmélete került feldolgozásra. Az első kiadás előszavában azt a tervemet is említettem, hogy azokat a fontos témákat, melyek kimaradtak (matroidok, poliéderes kombinatorika, rácsgeometria, blokkrendszerek, véges geometriák, stb.) egy második kötetben fogom feldolgozni. Itt a matematika túlszaladt az én terveimen: ezek a fejezetek olyan mértekben fejlődtek, hogy külön-külön köteteket töltenének ki, és a matematika egyre mélyebb eredményeit használják, túllépve azon a háttéranyagon, amire ez a könyv épül. Bár a feladat továbbra is csábít, e pillanatban meghaladja időm és energiám korlátait.
* * * |
A könyv fő célja, hogy a kombinatorika alapvető, elemi technikáinak elsajátítását segítse. Ennek leghatékonyabb (jóllehet meglehetősen időigényes) módja feladatok megoldásán át vezet. Ezért ez a könyv az anyagot feladatok és feladatsorok formájában tárgyalja (kivéve a fejezeteket bevezető általános észrevételeket). Annak a diáknak kíván segítséget nyújtani, aki a gráfelmélet, kombinatorika vagy alkalmazásai területén kíván kutatásba kezdeni, és azoknak a matematikusoknak, akik úgy érzik, hogy kombinatorikus technikák segíthetik kutatásaikat a matematika, operációkutatás, mérnöki tudományok stb. területén. A feladatok megoldásához szükséges matematikai háttér csak elemi lineáris algebra, csoportelmélet, valószínűségszámítás és analízis; a feladatok megoldása azonban a matematikai gondolkodásmódban való jelentős jártasságot igényel. A tisztelt olvasó számítson arra, hogy egy-egy feladat megoldásához általában többféle ötlet kipróbálásán keresztül lehet csak eljutni, (és emellett néha még jelentősebb számolást is kell végezni), és ne élje meg kudarcként, ha ez órákat, vagy akár napokat is igényel (merem állítani, hogy megéri). Különösen áll ez a csillaggal megjelölt problémákra, melyeket a legnehezebbnek érzek. A feladatok többsége nem magában áll, hanem olyan sorozathoz tartozik, mely lépcsőhöz hasonlóan vezet el az utolsó, legmélyebb eredményhez.
A könyv három fő részre oszlik: Feladatok, Ötlettár és Megoldások. A témában kevésbé jártas olvasó elolvashatja az Ötlettárban megadott ötletet is, mielőtt hozzálát a feladat megoldásához. A könyvben leírt ötletet és megoldást akkor is érdemes megnézni, ha az olvasó megoldotta a feladatot: lehet, hogy a leírt megoldásban olyan ötlet, fogás szerepel, mely egy későbbi feladat megoldásához nélkülözhetetlen. (Az olvasást az ötlettárban leírtakkal kezdjük; gyakran kerül ott olyan fogalom, vagy jelölés bevezetésre, mely a megoldásban nincs megismételve).
A feladatok állításainak eredeti szerzőjére a megoldás végén hivatkozom, nem adom azonban meg az eredeti cikk adatait az olyan eredmények esetében, melyek sok közkeletű tankönyvben és monográfiában tárgyalva vannak (ilyen művek egy listáját találhatjuk a könyv végén). Ha nincs hivatkozás, akkor az eredmény vagy (tudomásom szerint) új, vagy annyira közismert „folklór”, hogy nehéz volna az eredetét kinyomozni. A felhasznált kombinatorikai fogalmak vagy a feladat szövegében, vagy könyv végén található kislexikonban vannak definiálva. Itt található a jelölések listája, valamint a név- és tárgymutató is.
Köszönetnyilvánítás. Első helyen tanáraimnak, Erdős Pálnak és Gallai Tibornak tartozom hálával: ők szerettették meg velem a kombinatorikát, és alapjaiban tőlük tanultam azt, amit itt megírtam. E sorban meg kell említenem T. Sós Verát és Hajnal Andrást is. Rábai Tanár Úrnak a feladatgyűjtemény ötletét köszönöm.
Sok kombinatorikusnak tartozom köszönettel.
J. C. Ault, Babai László, Bacsó Gábor,
A. J. Bondy, Boros Endre, Csizmazia Tibor, Füredi Zoltán,
Katona Gyula, M. D. Plummer, és Simonovits Miklós az első
és masodik kiadás kéziratát és korrektúráját javították sok fontos
javaslattal és ötlettel. A megjelenés után sok további észrevételt
kaptam kollégáktól; többnek az értékét különösen növelte, hogy a
könyvből tanított kurzus során születtek. Ki kell emelnem
J. Burghduff, Frank András, F. Galvin,
D. E. Knuth, és I. Tomescu nevét. Külön hálával
tartozom D. E. Knuth-nak és D. Aldous-nak azért,
hogy a második kiadás új probláma-sorozatára olyan gyorsan küldték
el értékes megjegyzeséseiket, hogy azokat még a nyomdába adás előtt
figyelembe lehetett venni. Fried Katinak köszönöm a 2. kiadás
gondos
De mindenek felett feleségemnek, Vesztergombi Katinak kell megköszönnöm, hogy töretlen szakmai, technikai támogatásával és bátorításával lehetővé tette a könyv megírását, majd újabb kiadásait, beleértve a jelen kiadás mintegy felének gondos magyarra fordítását is. A másik felének ugyanilyen gondos fordításáért Márta lányomnak tartozom köszönettel (ő az első kiadáshoz azzal járult hozzá, hogy nem sírt túl sokat éjjel…)
Budapest és New Haven, 1999 január.