KAIST Discrete Math Seminar

The class of structures that admit near-unanimity functions is of interest in the field of computational complexity as they yield constraint satisfactions problems that are solvable in deterministic log-space. In the literature, there are diverse characterisations near-unanimity structures, but none that make the generation of all such graphs transparent. We present a new description of reflexive graphs and irreflexive symmetric graphs admitting near-unanimity functions. This description brings together many of the known descriptions, and provides a good picture of near unanimity graphs.
This is joint work with Tomas Feder, Pavol Hell, Benoit Larose, Cindy Loten and Claude Tardif.