Predavatelj: Martin Milanič
Ekvistabilni grafi so grafi, za katere obstaja linearen funkcional, ki karakterizira maksimalne neodvisne množice grafa. (Neodvisna množica v grafu je množica paroma nepovezanih točk.) Leta 2009 je Jim Orlin postavil domnevo, da je vsak ekvistabilni graf splošni particijski graf, tj., presečni graf take družine D podmnožic končne množice S, da maksimalne neodvisne množice grafa ustrezajo natanko particijam množice S z elementi iz družine D.
Znano je, da je Orlinova domneva pravilna za razred tetivnih grafov in za grafe brez asteroidalnih trojic. Če domneva drži tudi v splošnem, podaja kombinatorično karakterizacijo ekvistabilnih grafov. Na predavanju bomo razložili znane relacije med splošnimi particijskimi grafi, ekvistabilnimi grafi in t.i. trikotniškimi grafi ter obravnavali nekaj delnih rezultatov o Orlinovi domnevi. Med drugim bomo predstavili popolno karakterizacijo ekvistabilnih grafov, ki so netrivialni kartezični ali tenzorski produkti.
Skupno delo s Štefkom Miklavičem.
