Browsing by Author "Seyffarth, Karen"
Now showing 1 - 7 of 7
Results Per Page
Sort Options
- ItemOpen AccessAn Analysis of Countable Sublattices of Free Lattices(2016) Chan, Brian; Laflamme, Claude; Woodrow, Robert; Seyffarth, Karen; Cockett, Robin; Laflamme, Claude; Woodrow, RobertThis thesis investigates which lattices are countable sublattices of free lattices. This is equivalent to determining which lattices are sublattices of the free lattice on three generators. Our investigation is based on the following open problem (see \cite{FL}, 1995): ``Which lattices (and in particular which countable lattices) are sublattices of a free lattice?'' We describe how stronger variants of the semidistributive laws have contributed to our current understanding of sublattices of free lattices. In particular, we see how the strongest results known only apply to certain classes of countables lattices. Afterwards, we propose a strategy for analyzing the following class of countable lattices: finite width sublattices, L, of free lattices, where L is in a semidistributive variety.
- ItemOpen AccessComputing A-Homotopy Groups of Graphs Using Coverings and Lifting Properties(2018-09-21) Hardeman, Rachel; Bauer, Kristine; Seyffarth, Karen; Laflamme, Claude; Cunningham, CliftonIn classical homotopy theory, two spaces are homotopy equivalent if one space can be continuously deformed into the other. This theory, however, does not respect the discrete nature of graphs. For this reason, a discrete homotopy theory that recognizes the difference between the vertices and edges of a graph was invented, called A-homotopy theory. In classical homotopy theory, covering spaces and lifting properties are often used to compute the fundamental group of a space. In this thesis, we develop the lifting properties for A-homotopy theory. Using a covering graph and these lifting properties, we compute the fundamental group of the cycle C_5 and use this computation to show that C_5 is not contractible in this theory, even though the cycles C_3 and C_4 are contractible.
- ItemOpen AccessCreating, understanding and teaching mathematics: complementary processes(2012) Rapke, Tina; Towers, Jo; Seyffarth, KarenThe purpose of this dissertation is to explore the relationships among understanding, creating and teaching mathematics. It includes two pairs of complementary mathematics and education papers. The papers are complementary in the sense that the education papers draw on the experiences of creating the mathematics that appear in the mathematics papers and in doing so, provide insight into how the mathematical concepts, theorems and proofs are constructed. The education papers not , only provide insight into one mathematician's creating of mathematics, but mine the experiences and insights for their pedagogical implications.
- ItemOpen AccessDynamic and Self-stabilizing Distributed Matching(2003-01-28) Chattopadhyay, Subhendu; Higham, Lisa; Seyffarth, KarenSelf-stabilization is a unified model of fault tolerance. A self-stabilizing system can recover from an arbitrary transient fault without re-initialization. Self-stabilization is a particularly valuable attribute of distributed systems since they are tipically prone to various faults and dynamic changes. In several distributed applications, pairing of processors connected in a network can be viewed as a matching of the underlying graph of the network. A self-stabilizing matching algorithm can be used to build fault tolerant pairing of clients and servers connected in a network. First contribution of this report is an efficient, dynamic and self-stabilizing mazimal matching algorithm for arbitrary anonymous networks. The algorithm implements a locally distinct label generation technique that can be used by other applications. The second contribution of this report is a dynamic and self-stabilizing maximum matching alrogithm for arbitrary biparite networks. This is the first distributed amximum matching algorithm for networks containing cycles.
- ItemOpen AccessSmall cycle double covers and line graphs(1998) Fish, Jocelyn M.; Seyffarth, Karen
- ItemOpen AccessSome Problems on Graphs and Arrangements of Convex Bodies(2017) Khan, Muhammad Ali; Bezdek, Károly; Pivovarov, Peter; Ling, Joseph; Woodrow, Robert; Seyffarth, KarenArrangements of convex bodies are ubiquitous in discrete geometry. Covering and packing problems are two major classes of problems arising from these arrangements. This thesis makes contributions to some open questions on covering a convex body by its homothetic copies and packings of translates of a convex body. The packings we study lead to the notion of a contact graph, a tool used by mathematicians, material scientists and physicists while investigating these packings. This brings a combinatorial flavour to this thesis and leads to the algorithmic question of generating graphs and hypergraphs with desired properties. We introduce the covering index of a convex body as a measure of how economically the body can be covered by a relatively few smaller positive homothetic copies. Determining the covering index can be thought of as a quantitative version of the sixty-year old Covering Conjecture in discrete and convex geometry. We prove several interesting properties of the covering index, compute its values for large classes of convex bodies and use it to devise an approach to attack the Covering Conjecture. We then consider the problem of determining the separable Hadwiger number of a smooth convex domain and the maximum contact numbers of totally separable translative packings of a smooth strictly convex domain. Both these questions have links with crystallography and self-assembly of material particles, and are completely solved here. Moreover, we show that for smooth Radon domains the extremal packings always lie on special kinds of lattices and characterize the underlying contact graphs. Next, we fully address the algorithmic questions of constructing tournaments from their imbalance sets and hypertournaments from their score sequences. The former relates to the Equal-Sum Subsets problem from computer science, while the latter is a special instance of the degree sequence problem that asks for the generation of all graphs or hypergraphs in some large class that have the same degree sequence. We characterize imbalance sets of tournaments, give an algorithm to generate tournaments from their imbalance sets and define a rapidly mixing Markov chain that uniformly samples all hypertournaments with a given score sequence.
- ItemOpen AccessThe distinguishing chromatic number of wreath products(2010) Hodgins, Cameron; Seyffarth, Karen