Izbrane teme o grafih, hipergrafih in Boolovih funkcijah

Projekt se osredotoča na dve glavni smeri raziskovanja, ki povezujeta grafe in hipergrafe ter delno tudi Boolove funkcije. Prva linija raziskovanja je povezana z raziskavami 3-uniformnih hipergrafov. Izhodišče je dobro znan odprt problem v zvezi z obstojem ‘popolnoma kombinatornega’ polinomskega časovnega algoritma za prepoznavanje pragovnih hipergrafov (ali, kar je enakovredno, pragovnih monotonih Boolovih funkcij, podanih s popolno DNO). Druga linija raziskav se ukvarja s konceptom v teoriji grafov, imenovanim klično dualno konformni grafi. Ta koncept je tesno povezan z dualno konformnimi hipergrafi, pojmom, uvedenim v prejšnjem bilateralnem sodelovanju med projektnima skupinama. Na podlagi začetnih rezultatov za razred KDK grafov je cilj v tem delu projekta raziskati nadaljnje strukturne in algoritmične lastnosti KDK grafov ter tovrstne grafe karakterizirati v posebnih primerih.