Category Archives: Yr 4 Description 2021/2022

Please click Older Posts at the bottom of the page and subsequent pages for further project descriptions.

Covering spaces and subgroups of free groups

Code: UP2122C

Supervisor: Ulrich Pennig

Project Description:
The fundamental group of a topological space, which we encountered in the algebraic topology course, is defined as the homotopy classes of based loops in the space, where the group multiplication is induced by concatenation. The fundamental group of the torus is generated by two such loops a and b. These commute, i.e. they satisfy ab = ba. Now consider the topological space obtained by gluing together two circles at a chosen base point, which looks like the figure 8. The fundamental group of this space is also generated by two elements, but this time there are no relations among them: The fundamental group is the free group on two generators.

The first goal of this project is to understand the definition of free groups and, more generally, amalgamated products of groups. We will then prove the theorem that subgroups of free groups are again free. This purely algebraic statement has a beautiful proof based on the theory of covering spaces. In the lecture we have already seen how the real line covers the circle in the sense that there is a map to the circle, such that preimages of neighbourhoods look like multiple copies of themselves. During the course of the project we will understand the basics of covering space theory, discuss coverings and fundamental groups of graphs and finally prove the result mentioned above.

Type: Year 4 MMath Project

Prerequisite modules:
– Algebraic Topology (MA3008)
– Groups (MA0213) or Algebra II: Rings (MA3013)

Max. number of students: 1

Dimension Reduction and Classification Algorithms. Supervisor: Dr. A. Artemiou

Title of Project: Dimension Reduction and Classification Algorithms

Code: AA2122A

Supervisor: Dr A. Artemiou

Project description:
Data mining and dimension reduction are two topics which receive great attention in the big data era we are in. There are a number of algorithms which were proposed to discuss data mining algorithms (like Support Vector Machines) and dimension reduction algorithms (like Sufficient Dimension Reduction). Recently, the two areas were combined to create new algorithms for dimension reduction in regression using ideas from the data mining literature. This created a class of new algorithms that perform very well and are able to do linear and nonlinear dimension reduction in a unified framework.
The project objective is to create first new algorithms for data mining by combining existing algorithms. The student will review the given literature and then derive results for new methodology for classification. The performance of the new algorithm will be evaluated using real datasets. Then, the algorithms will be used to perform dimension reduction to regression problems based on existing literature. Good programming skills are essential for this project. (In 2017-2018 a student work on this project and developed a modified version of SVM)

Prerequisite 3rd year module:
MA2500: Foundations of Probability and Statistics;
MA 2501: Programming and Statistics
and MA3505: Multivariate Statistics is helpful but not essential.

Number of students who can be supervised on this project:
1

Alternate paths and matchings in graphs – Supervisor: Dr Andrei Gagarin

Project title: Alternating paths and matchings in graphs

Name of supervisor: Dr Andrei Gagarin

Code: AG2122A

Project Description:

Background

Matchings play an important role in graph theory and applications, for example, in assignment problems, where pairs of items are to be matched together (e.g. if people are to be assigned to jobs). The problem of finding a maximum (by cardinality) matching in a given graph G=(V,E) is solvable in polynomial time. The Hungarian algorithm allows us to find a maximum-size matching in a bipartite graph, and the Edmonds’ blossoms algorithm extends the ideas of efficient usage of alternating paths to non-bipartite graphs. A variation of the problem consists in finding a smallest weight/cost maximum matching in weighted graphs.

Objectives

The objectives of this project consist in studying literature related to the theory of matchings and alternating paths in graphs, their applications, and the Hungarian algorithm and the Edmonds’ blossoms algorithm to find a maximum matching in a graph. The student will need to implement the Hungarian algorithm and run experiments on either artificially generated or some real-world instances of the problem. Another objective is to study the Edmonds’ blossoms algorithm and to understand the proof of its correctness. The minimum/maximum cost maximum-size matchings in weighted graphs and integer linear problem formulations are to be considered as well.

Approach

Study of literature on alternating paths and matchings from the points of view of Graph Theory, algorithms, and applications. Implementing the Hungarian algorithm and running computational experiments on some artificially generated or real-world instances and comparing the computational outcomes. Considering maximum-size matchings in weighted graphs and integer linear programming formulations of the problems, using generic LP/IP solvers.

References:

1.            W.L. Kocay, D.L. Kreher, Graphs, Algorithms, and Optimization, 2nd ed., CRC Press, 2017, Chapter 9.

2.            D. Karapetyan, A.J. Parkes, G. Gutin, A. Gagarin, Pattern-based approach to the workflow satisfiability problem with user-independent constraints, Journal of Artificial Intelligence Research 66 (2019), pp. 85-122.

3. W.L. Winston, Operations Research: applications and algorithms, 4th ed., Thomson-Brooks/Cole, 2004, Section 7.5.3.

Deliverables

A report (dissertation/thesis) and software implementing the Hungarian algorithm to solve the problem in weighted and/or unweighted graphs, together with problem instances used in computational experiments.

Prerequisites

An interest in and some knowledge of graph theory, modeling of real-life problems on graphs, as well as some computer programming skills using data structures to solve problems on graphs and combinatorial structures.

Inflation Instabilities in Nematic Elastomer Tubes – Supervisor: Dr Angela Mihai

Title: Inflation Instabilities in Nematic Elastomer Tubes

Code: AM2122B

Project Description:

Nematic liquid crystal elastomers are advanced multifunctional
materials that combine the exibility of polymeric networks with the ne-
matic structure of liquid crystals. Due to their complex molecular architec-
ture, they are capable of exceptional responses, such as large spontaneous
deformations and phase transitions, which are reversible and repeatable
under certain external stimuli (e.g., heat, light, solvents, electric or mag-
netic elds). Their accurate description requires multiphysics modelling
combining elasticity and liquid crystal theories.

In particular, internally pressurised hollow spheres and tubes are relevant
in many engineering and biomedical applications. This project focuses
on ination instabilities in a nematic circular cylindrical tube where the
liquid crystal mesogens may rotate during deformation. Assuming dier-
ent material models for ideal nematic elastomers, the aim is to show that,
depending on the particular model, the required internal pressure may in-
crease monotonically, or increase and then decrease, or increase, decrease,
and then increase again. A comparison with similar phenomena in purely
elastic tubes will also be performed.

Type: 20 credits

Supervisor: Dr Angela Mihai

Prerequisite modules: (2nd year) Real Analysis, Calculus of Several Variables, Linear Algebra; (3rd year) Partial Differential Equations, Methods of Applied Mathematics, Finite Elasticity

Maximum number of students: 1

Viscosity solutions and homogenisation – Supervisor: Dr Federica Dragoni

Title of Project:
Viscosity Solutions and Nonlinear Partial Differential Equations

Code: FD2122B

Supervisor: Dr. F. Dragoni

Project description:
Nonlinear partial differential equations (PDEs) describe many phenomena
in sciences and economics, e.g. the value of an optimal control problem,
minimal surfaces, porous media, conservation laws, etc. Solutions to these
equations are often not sufficiently regular in order to write all the derivatives
appearing in the equation (e.g. they can be just continuous and not
differentiable). So the solutions have to be understood in a suitable generalized
sense. We consider the so-called viscosity solutions which consist
in using sufficiently smooth test functions to approximate from above and
below a unique continuous solution for a very large class of first-order and
second-order PDEs.
A project would consist of an introduction to the general theory of viscosity
solutions and applications to a specific nonlinear PDE (e.g. Hamilton-Jacobi
eq.s, infinite-Laplace eq., p-Laplace eq., etc.). One possibility is to investigate
the relation between viscosity solutions and control theory or games
theory. Another possibility is to focus on degenerate elliptic/parabolic equations
(e.g. the evolution by mean curvature flow) or the relations with convexity.
If required, it will be possible to deal with more geometric equations
(space-dependent) and metric formulas. One possibility is to investigate the
relation between viscosity solutions and control theory or games theory.

Project offered a double module, single module, or both:

Prerequisite 3rdd year modules:
The following classes may be helpful:
MA3303 Theoretical and Computational PDEs

Number of students who can be supervised on this project:
1

Reproducing kernel Hilbert C∗ -modules and applications to machine learning – Supervisor: Dr Bertrand Gauthier and Dr Gandalf Lechner

Title of project: Reproducing kernel Hilbert C∗ -modules and applications to machine learning

Code: GL2122B

Supervisors: Dr. B. Gauthier and Dr. G. Lechner

Project Description:

Project offered as double module, single module, or both: Double

Prerequisite modules: Functional and Fourier Analysis

Number of students who could be supervised for this project: 1–2

Year: 4