A 2004 article written by Yixun Lin and Aifeng Yang published in the journal Discrete Math characterized the set of a 3-cutwidth critical graphs by five specified elements. This project extends the idea to 4-cutwidth critical graphs.

The simple relational structures form the units, or atoms, upon which all other relational structures are constructed by means of the substitution decomposition. This decomposition appears to have first been introduced in 1953 in a talk by Fraïssé, though it did not appear in an article until a paper by Gallai in 1967. It has subsequently been frequently rediscovered from a wide variety of perspectives, ranging from game theory to combinatorial optimization. Of all the relational structures - a set which also includes graphs, tournaments and posets - permutations are receiving ever increasing amounts of attention. A simple permutation is one that maps every nontrivial contiguous set of indices to a set of indices that is never contiguous. Simple permutations and intervals of permutations are important in biomathematics, while permutation classes - downsets under the pattern containment order - arise naturally in settings ranging from sorting to algebraic geometry. We begin by studying simple permutations themselves, though always aim to establish this theory within the broader context of relational structures. We first develop the technology of "pin sequences", and prove that every sufficiently long simple permutation must contain either a long horizontal or parallel alternation, or a long pin sequence. This gives rise to a simpler unavoidable substructures result, namely that every sufficiently long simple permutation contains a long alternation or oscillation. ErdÅ s, Fried, Hajnal and Milner showed in 1972 that every tournament could be extended to a simple tournament by adding at most two additional points. We prove analogous results for permutations, graphs, and posets, noting that in these three cases we may need to extend a structure by adding (n+1)/2 points in the case of permutations and posets, and logâ (n+1) points in the graph case. The importance of simple permutations in permutation classes has been well established in recent years. We extend this knowledge in a variety of ways, first by showing that, in a permutation class containing only finitely many simple permutations, every subset defined by properties belonging to a finite "query-complete set" is enumerated by an algebraic generating function. Such properties include being an even or alternating permutation, or avoiding generalised (blocked or barred) permutations. We further indicate that membership of a permutation class containing only finitely many simple permutations can be computed in linear time. Using the decomposition of simple permutations, we establish, by representing pin sequences as a language over an eight-letter alphabet, that it is decidable if a permutation class given by a finite basis contains only finitely many simple permutations. We also discuss possible approaches to the same question for other relational structures, in particular the difficulties that arise for graphs. The pin sequence technology provides a further result relating to the wreath product of two permutation classes, namely that C â D is finitely based whenever D does not admit arbitrarily long pin sequences. As a partial converse, we also exhibit a number of explicit examples of wreath products that are not finitely based.

Probability theory is a branch of mathematics concerned with determining the long run frequency or chance that a given event will occur. This chance is determined by dividing the number of selected events by the number of total events possible, assuming these events are equally likely. Probability theory is simply enumerative combinatorial analysis when applied to finite sets. For a given finite sample space, probability questions are usually "just" a lot of counting. The purpose of this thesis is to provide some in depth analysis of several combinatorial methods, including basic principles of counting, permutations and combinations, by specifically exploring one type of probability problem: C ordered possible elements that are equally likely s independent sampled subjects r distinct elements, where r = 1, 2, 3, …, min (C, s) we want to know P(s subjects utilize exactly r distinct elements). This thesis gives a detailed step by step analysis on techniques used to ultimately finding a general formula to solve the above problem.

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Doctor of Philosophy. Johannesburg, 2016. / In this thesis, various partition functions with respect to Rogers-Ramanujan identities and George Andrews' partitions with initial repetitions are studied. Agarwal and Goyal gave a three-way partition theoretic interpretation of the Rogers- Ramanujan identities. We generalise their result and establish certain connections with some work of Connor. Further combinatorial consequences and related partition identities are presented. Furthermore, we re ne one of the theorems of George Andrews on partitions with initial repetitions. In the same pursuit, we construct a non-diagram version of the Keith's bijection that not only proves the theorem, but also provides a clear proof of the re nement. Various directions in the spirit of partitions with initial repetitions are discussed and results enumerated. In one case, an identity of the Euler-Pentagonal type is presented and its analytic proof given. / M T 2016

A well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger, Mireille Bousquet-Mlou, Thomas Prellberg, Neal Madras, Gordon Slade, Agnes Dit- tel, E.J. Janse van Rensburg, Harry Kesten, Stuart G. Whittington, Lincoln Chayes, Iwan Jensen, Arthur T. Benjamin, and many others. More than three hundred papers and a few volumes of books were published in this area. A SAW is interesting for simulations because its properties cannot be calculated analytically. Calculating the number of self-avoiding walks is a common computational problem. A recently proposed model called prudent self-avoiding walks (PSAW) was first introduced to the mathematics community in an unpublished manuscript of Pra, who called them exterior walks. A prudent walk is a connected path on square lattice such that, at each step, the extension of that step along its current trajectory will never intersect any previously occupied vertex. A lattice path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. We will discuss some enumerative problems in self-avoiding walks, lattice paths and walks with several step vectors. Many open problems are posted. / by Shanzhen Gao. / Thesis (Ph.D.)--Florida Atlantic University, 2011. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.

Thesis (M.S.)--Rochester Institute of Technology, 2004. / Typescript. Includes bibliographical references (leaves 71-75).

Thesis (doctoral)--Rijksuniversiteit Groningen, 2002. / Includes bibliographical references (p. 189-202).

Thesis (Ph. D.)--Rutgers University, 2008. / "Graduate Program in Physics and Astronomy." Includes bibliographical references (p. 81-85).

Dissertation (D.M.A.)--The University of North Carolina at Greensboro, 2009. / Directed by John Salmon; submitted to the School of Music. Title from PDF t.p. (viewed May 17, 2010). Includes bibliographical references (p. 47-48).

Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaf 39).