Information theoretic parameters for graphs and operator systems

  • Gareth Boreland

Student thesis: Doctoral ThesisDoctor of Philosophy


This thesis explores connections between information theory and graph theory. We prove a number of seemingly new results on graph entropy, a classical information theoretic quantity introduced by Korner. Our work includes the determination of the graph entropy of the odd cycles and their complements under certain probability distributions.

We develop a theory of convex corners in finite dimensional spaces of matrices appropriate for applications in quantum information, and discuss the concept of entropy over a convex corner. We recall the definition of a non-commutative graph from the work of Duan, Severini and Winter, and with a given non-commutative graph we associate a number of convex corners, before proving a "quantum sandwich theorem".

We define several new parameters for non-commutative graphs, and show them to be generalisations of the corresponding graph parameters. This includes two quantum versions of the Lovasz number, one of which is seen to be an upper bound on the Shannon capacity of an associated quantum channel.

Finally we return to examine graph entropy in the case of a non-i.i.d. classical source, and attempt to generalise the Kolmogorov-Sinai entropy of a dynamical system to this setting.
Date of AwardJul 2020
Original languageEnglish
Awarding Institution
  • Queen's University Belfast
SponsorsNorthern Ireland Department for the Economy
SupervisorIvan Todorov (Supervisor) & David Barnes (Supervisor)

Cite this