Jack Neubecker

Hamilton decompositions of two-ended infinite graphs

November 19, 2020November 10, 2024Posted in Combinatorics, Graphic design, ResearchTagged alspach and rosenfeld's conjecture, alspach's conjecture, bermond's conjecture, cayley graph, Combinatorics, hamilton cycle, hamilton decomposition, hamilton double-ray, infinite graph, locally finite graph

I recently submitted my honours thesis, and for posterity (or anybody who might actually be interested) it is available for download as a PDF here.

jack_neubecker_thesis_nov_2020 Download

Abstract

A Cayley graph $Cay(\Gamma, S)$ is a graph with vertex set the elements of the group $\Gamma$ , and edge set $\{\{u,v\} \mid v = u + s, s \in S \subset \Gamma\}$ . A Hamilton cycle is a closed path which visits every vertex in a graph exactly once, and a Hamilton decomposition of a graph is a partition of its edge-set into Hamilton cycles. It has been conjectured by Alspach that every connected $2k$ -regular Cayley graph of a finite abelian group has a Hamilton decomposition. Another conjecture from Alspach and Rosenfeld says that if $G$ is a 3-connected, 3-regular graph with a Hamilton cycle, then the Cartesian product $G \square K_2$ is Hamilton decomposable. Bermond also conjectures that if two graphs are Hamilton decomposable, then their Cartesian product is also Hamilton decomposable. These three conjectures remain open, and we examine their infinite generalisations. Specifically, we study two-ended infinite abelian groups, and the Cartesian product $G \square P_\infty$ , where $G$ is an even-regular finite graph and $P_\infty$ is a two-way infinite path. The notion of a Hamilton cycle can be generalised to infinite graphs as a spanning two-way infinite path. However, if the graph has two ends, some graphs contain an end-separating edge-cut which differs in parity from the number of paths in the decomposition, precluding the existence of a decomposition into spanning two-way infinite paths. The question, then, is whether this is the only obstruction to a Hamilton decomposition. We show that if $G$ is 2, 4, or 6-regular, and has a Hamilton decomposition, then $G \square P_\infty$ has a Hamilton decomposition if it avoids the obstruction. We show that a two-ended Cayley graph with only one non-torsion generating element can be viewed as a graph of the form $G \square P_\infty$ , and thus complete the case of the generalisation of Alspach’s conjecture for two-ended, 6-regular Cayley graphs of infinite abelian groups with only one non-torsion generating element. We further investigate the existence of a Hamilton decomposition of $G \square P_\infty$ if $G$ has a Hamilton cycle, but not a Hamilton decomposition, and construct a backtracking algorithm to test the generalisation of Alspach’s conjecture and our techniques, in the cases which remain unproven. An infinite family of positive solutions is provided in this unproven case, as well as examples which do not fit the techniques used.

Keywords

Hamilton cycle, Hamilton decomposition, graph, Cayley graph, Hamilton double-ray, Alspach’s Conjecture, Bermond’s Conjecture, Alspach and Rosenfeld’s Conjecture, infinite graph, locally finite graph.

Evolutionary Algorithms – A Brief Overview

August 23, 2020November 29, 2023Posted in Probability and StatisticsTagged data science, evolutionary algorithm, genetic algorithm, machine learning

Last year, as part of the assessment for a machine learning course, we were asked to write a tutorial paper on a topic of our choice. I chose to write about Evolutionary Algorithms. I’m happy with how it turned out, and the lecturer chose it as an exemplar for future students. For posterity, I’m going to share it here. Unfortunately, the original .tex file is lost to the sands of time (more specifically, it was saved on a thumb drive that was the only casualty in a backpack-dropping accident while getting off the bus). Thus, the only copy I have access to is the PDF file that I submitted online. You can find that here:

evolutionary-algorithms Download

SCIE3250 Project – Speed and Complexity of Bayesian Network Selection Using Continuous Evolutionary Techniques

July 31, 2019November 29, 2023Posted in Probability and Statistics

Abstract

Choosing a Bayesian network which best explains the dependencies in a dataset is an important problem in scientific areas including medicine, epidemiology, genetic analysis and domino effect analysis. However, inference using Bayesian belief networks is an NP-hard problem, and inference is considered computationally demanding even for feasible problems. With these conditions, it is generally hoped that a small army of algorithms can be developed which will find almost optimal solutions, and these are then all applied to a given problem and the best result taken. We therefore aim to provide an alternative family of methods using continuous evolutionary global optimisation techniques, and quantify its effectiveness compared with the already available hill-climbing method. Various implementations are considered, and it is found that combining available continuous global optimisation packages with the pre-existing score function is computationally unfeasible for even small networks. Potential reasons are discussed, and improvements proposed using custom-built methods, based on the effectiveness of the existing hill climbing algorithm.

The full PDF can be downloaded here, and the presentation PDF can be downloaded here.