Հիպերգրաֆները ցույց են տալիս լուծում 50-ամյա խնդրին

1973 թվականին Պաուլ Էրդոշը հարցրեց, թե արդյո՞ք հնարավոր է հավաքել «եռյակների» հավաքածուներ՝ երեք կետ գրաֆիկի վրա, այնպես, որ դրանք պահպանեն երկու անհամատեղելի թվացող կանոններ։ Նոր ապացույցը ցույց է տալիս, որ դա միշտ կարելի է անել։

1850 թվականին մաթեմատիկոս Թոմաս Փենինգթոն Քըրքմենը, երբ չէր կատարում իր հիմնական՝ Անգլիայի եկեղեցու տեղապահի պարտականությունը, գրեց իր «աշակերտուհու խնդիրը»․ «Դպրոցում տասնհինգ օրիորդներ յոթ օր հաջորդաբար դուրս են գալիս երեք-երեք իրար կողքի։ Պահանջվում է նրանց օրերորվ դասավորել այնպես, որ այդ յոթ օրերում ոչ մի երկու աղջիկ երկրորդ անգամ չքայլի կողք կողքի (երկու աղջիկ քայլեն կողք կողքի միայն մեկ անգամ)։

Ժամանակակից մաթեմատիկոսի համար այս խնդիրը լավագույնս պատկերացնելի է հիպերգրաֆի տեսքով՝ երեք կամ ավելի խմբերում դասավորված գագաթների շարքով (գագաթ կամ հատման կետ՝ կետ դիագրամում, որտեղ գծերը հանդիպում են իրար կամ որից դրանք դուրս են գալիս, ճառագայթի սկզբնակետ)։ Տասնհինգ աշակերտուհիները գագաթներ են, և «երեքը՝ կողք կողքին» կարելի է դիտարկել որպես եռանկյուն՝ երեք գծերով և երեք եզրերով, որոնք միացնում են երեք գագաթ։

Քըրքմենի խնդիրը, ըստ էության, հարցնում է, թե արդյոք կա եռանկյունների դասավորություն, որը կապում է բոլոր աշակերտուհիներին, բայց այն հավելյալ սահմանափակմամբ, որ ոչ մի երկու եռանկյուն չունենան ընդհանուր գագաթ։ Ընդհանուր գագաթ ունենալը կնշանակեր, որ երկու աշակերտուհիներ պետք է քայլեն միմյանց հետ մեկից ավել անգամ։ Այս նոր սահմանափակումը նշանակում է, որ յուրաքանչյուր աղջիկ քայլում է երկու նոր ընկերների հետ մեկ շաբաթ շարունակ ամեն օր, որպեսզի ամեն հնարավոր զույգ հավաքվի միայն մեկ անգամ։

Այս խնդիրները և դրա նմանները հրապուրել են մաթեմատիկոսներին ավելի քան երկու դար՝ սկսած այն պահից, երբ Քըրքմենն առաջադրեց իր հարցը։ 1973 թվականին լեգենդար մաթեմատիկոս Պաուլ Էրդոշը առաջ է քաշել նման մի հարց։ Նա հարցրեց, թե արդյո՞ք հնարավոր է կառուցել մի հիպերգրաֆ երկու թվացյալ անհամատեղելի հատկություններով։ Նախ՝ յուրաքանչյուր գագաթ պետք է միացված լինի միայն մեկ եռանկյան, ինչպես աշակերտուհիների դեպքում է։ Այս հատկությունը դարձնում է հիպերգրաֆը եռանկյուններով խիտ լցված։ Երկրորդը՝ պահանջվում է, որ եռանկյունների ցանկացած փոքր խմբի համար լինի առնվազն երեքով ավելի գագաթ, քան եռանկյուն։ «Կա այս փոքր հակասականությունը, որտեղ կա ընդհանուր խիտ պատկեր, որը չունի խիտ մասեր» ,- ասել է Կալիֆոռնիայի տեխնոլոգիական ինստիտուտի մաթեմատիկոս Դեյվիդ Քոնլոնը։

Աղբյուրը՝ quantamagazine.org