Cayley partial cubes

Abstract

This thesis explores partial cubes, a well-studied class of graphs that can be isometrically embedded into hypercubes, with a particular focus on those that are also Cayley graphs. A central result is a modern and mostly self-contained reconstruction of the proof that Cayley graphs of finite Coxeter groups are partial cubes, clarifying a classical but often fragmented argument. The second major contribution is the construction of non-Coxeter Cayley partial cubes, built from perfect codes in finite fields. These examples demonstrate that not all Cayley partial cubes arise from Coxeter groups, refuting a long-standing conjecture.