School of Mathematics and Statistics - Theses
Permanent URI for this collection
Search Results
1 - 4 of 4
-
ItemCombinatorial enumeration and the Bethe Ansatz( 2017)This thesis focuses on combinatorial enumeration of lattice paths using the Constant Term method. In particular we make use of the Bethe Ansatz, an Ansatz given by a linear combination of solutions to the free ``no boundaries'' problem (these solutions are called ``bulk'' solutions). We begin with a short review of these enumeration methods using the simple example of Dyck paths, and provide an example as to how the Constant Term method lends itself to combinatorial understanding with a new bijection to weighted Dyck paths. We then move to more complicated lattice paths called Osculating Paths. Previous solutions to this problem gave ambiguous results due to the ill defined nature of the Constant Term of a rational function. The Constant Term has a simple definition if the argument is a Laurent series, but if the argument is a rational function then the value of the Constant Term depends on how the rational function is embedded into a ring of Laurent series (of which there are many possible). A careful choice of which embeddings to choose leads to a valid solution to the initial condition. A proof that the embedding satisfies the initial condition is provided, along with a combinatorial interpretation of why. This Rational Constant Term method is then used to solve the Alternating Sign Matrix problem as a lattice path problem. Interestingly this method produces a summation form for the enumeration of Alternating Sign Matrices, in contrast to the more familiar product form. It remains an open problem to find a connection between these summation and product forms, similar to that which has been found for many non-intersecting path problems. The latter half of this thesis focuses on the broader application and limits of the Constant Term method. We consider nearest neighbour walks in the quarter-plane and eighth-plane, considering which step sets are readily solvable and why. These chapters consider the connection between the Constant Term and the method of images, using reflection groups to satisfy the boundary conditions. These step sets can be split into three types of reflection groups, orthogonal reflections across lines that pass through the origin, oblique reflections across lines that pass through the origin, and affine reflections (reflections across lines parallel to lines through the origin). We can further split the step sets into those with lines of reflection that align with the quarter-plane boundaries, and those with lines of reflection that cut through the quarter-plane. As the affine reflection group is infinite, it is not clear what form the Bethe Ansatz should take. For many problems an algebraic solution leads to a combinatorial understanding, but in solving these affine step sets the combinatorics of the problem leads to an algebraic solution. This method requires an infinite number of images to solve boundary conditions for finite lattice paths. The eighth-plane step set problems illustrate that care must be taken in writing down the partial difference equations. These paths are only satisfied if we can ensure that this diagonal boundary cannot be ``jumped'' by a single step in these paths.
-
ItemGeneralised directed walker models of adsorption and gelation( 2015)We outline an approach to constructing and solving models of highly interactive systems of single and multiple homopolymers, focusing on adsorption and gelation effects. In particular, solutions of our model allow us describe the critical behaviour of our system, such as the temperature required to graft a polymer onto an attractive surface or the potential energy required to bond a collection of single polymers into a branched, dense gel structure. We begin by outlining a simple counting problem of finding a closed-form expression for the number of walks along a finite lattice that obey some specified step constraints. Of particular relevance is the constraint of self-avoidance which specifies that a given walk is only able to visit a given site once, and we highlight why self-avoiding walks are considered a good approach to modelling polymer conformations. We further highlight how one can incorporate this purely combinatorial problem into the framework of statistical mechanics which allows us to construct a probabilistic model that links the microscopic and macroscopic state of a thermodynamic system. In short, we review the well established approach of transforming the task of modelling a physical system of single or multiple polymers into a combinatorial problem. We then show how self-avoiding directed walkers can be employed to construct idealised models of these polymer systems and review known techniques that allow us to establish exact solutions. While previous work on directed walker models has predominantly focused on, at most, single interaction effects, the applicability of these current techniques to solve more sophisticated models that incorporate multiple polymer conformations and multiple interaction effects was relatively unconsidered. Indeed, we will showcase the versatility of such techniques, central of which is the kernel method, and further unearth extensions of these techniques to solve for a number of highly interactive polymer models, with subsequent analysis revealing a rich set of interesting and unexpected critical behaviour.
-
ItemCombinatorial geometry of point sets with collinearities( 2014)In this thesis various combinatorial problems relating to the geometry of point sets in the Euclidean plane are studied. The unifying theme is that all the problems involve point sets that are not in general position, but have some collinearities. Topics addressed include; Dirac's conjecture related to the maximum degree of visibility graphs, Erdős' general position subset selection problem, connectivity properties of visibility graphs, visibility in bichromatic point sets, and empty pentagons in point sets with collinearities.
-
ItemCombinatorics of lattice paths and polygons( 2012)We consider the enumeration of self-avoiding walks and polygons on regular lattices. Such objects are connected with many other problems in combinatorics, as well as in fields as diverse as physics and chemistry. We examine the general models of walks and polygons and methods we can use to study them; subclasses whose properties enable a rather deeper analysis; and extensions of these models which allow us to model physical phenomena like polymer collapse and adsorption. While the general models of self-avoiding walks and polygons are certainly not considered to be ‘solved’, recently a great deal of progress has been made in developing new methods for studying these objects and proving rigorous results about their enumerative properties, particularly on the honeycomb lattice. We consider these recent results and show that in some cases they can be extended or generalised so as to enable further proofs, conjectures and estimates. In particular, we find that properties shared by all two-dimensional lattices allow us to develop new methods for estimating the growth constants and certain amplitudes for the square and triangular lattices. The subclasses of self-avoiding walks and polygons that we consider are typically defined by imposing restrictions on the way in which a walk or polygon can be constructed. Ideally the restrictions should be as weak as possible, so as to result in a model that closely resembles the unrestricted case, while still enabling some manner of simple recursive construction. These recursions can sometimes lead to solutions for generating functions or other quantities of interest. Some of the models we consider display quite unusual asymptotic properties despite the relatively simple restrictions which lead to their construction. We approach the modelling of polymer adsorption in several ways. Firstly, we adapt some of the new methods for studying self-avoiding walks on the honeycomb lattice to account for interactions with an impenetrable surface. In this way we are able to prove the exact value of the critical surface fugacity for adsorbing walks, confirming an existing conjecture. Then, we show that some key identities for the honeycomb lattice model lead to a new method for estimating the critical surface fugacities for adsorption models on the square and triangular lattices. Many of the estimates we obtain in this way are new; for the cases where previous estimates did already exist, our results are several orders of magnitude more precise. Finally, we define some new solvable models of polymer adsorption which generalise existing models, and find that some of these models exhibit interesting and unexpected critical behaviour.