# Ryan Kavanagh's Papers

Explorations on the Dimension of a Graph

Erdős, Harary and Tutte first defined the dimension of a graph $$G$$ as the minimum number $$n$$ such that $$G$$ can be embedded into the Euclidean $$n$$-space $$E_n$$ with every edge of $$G$$ having length 1. Although some have since extended the definition such that only adjacent vertices may be separated by a distance of 1, this paper will focus on the original definition. No general method is known for determining the dimension of an arbitrary graph $$G$$ but lower and upper bounds will be proven for arbitrary graphs. A sharp upper bound will be given for $$k$$-partite graphs by generalising the proofs presented by Erdős et al. for bipartite graphs and by Buckley et al. for tripartite graphs. New findings further include a lower bound and applications to various classes of graphs.

• December 2011
• PDF
A Primer on Provability Logic

The K4LR and GL systems of modal logic will be presented in the context of a Hilbert-style system of sentential logic. Löb's theorem and Löb's Derivability Criterion will be proven. Similarities between properties of $$Bew$$ and GL's $$\square$$ will be drawn, before proving that $$\square$$ in GL can be interpreted as $$Bew$$ in Peano arithmetic by means of realisations. The soundness of this interpretation will be proven by Solovay's arithmetical completeness theorem. From this, applications of GL will be considered, including a proof of Gödel's Second Incompleteness Theorem.

• April 2012
• PDF