- 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
- 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