The structure of near-unanimity graphs

2013/04/12 Fri 4PM-5PM – ROOM 3433

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.

This is joint work with Tomas Feder, Pavol Hell, Benoit Larose, Cindy Loten and Claude Tardif.

Tags: MarkSiggers