Izbrane teme o grafih, hipergrafih in Boolovih funkcijah / Selected topics on graphs, hypergraphs, and Boolean functions

(SI) 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.

(EN) The project focuses on two main lines of research connecting graphs and hypergraphs, and partly also Boolean functions. The first line of research is related to investigations of 3-uniform hypergraphs. The second line of research deals with a concept in graph theory called clique dually conformal graphs. Motivated by these initial observations of the class of CDC graphs, the project goal in this part is to investigate further structural and algorithmic properties of CDC graphs, and characterize them in special cases.