Yoke Graphs

יום א', 19/11/2017 - 14:00

A flip graph is a graph, on a set of objects, in which adjacency reflects local change. 

Flip graphs, from different domains, have surprising common properties, in terms of algebraic, combinatorial and metric properties.

In particular, they carry similar group actions, are intimately related to posets and have similar diameter formulas. 

In this work, we introduce a new family of flip graphs, the Yoke graphs, which generalizes several formerly considered graphs --

on triangulations, permutations and trees.


Our main result is the computation of the diameter of an arbitrary Yoke graph.

At the heart of the proof lies the idea of transforming a diameter evaluation to an eccentricity problem.


This work forms part of a PhD thesis written under the supervision of Ron Adin and Yuval Roichman.