Discrete Mathematics and Combinatorics Commons^™

Finding Combinatorial Patterns In Real Valued Omics Data, Kenneth Smith

Dissertations

Precision medicine is a healthcare approach which tailors disease prevention and treatment to an individual, based on their genetics, environment, lifestyle, and physiological state. These factors interact to produce biological changes that can be measured to produce data called omics, and include genomics, lipidomics, and proteomics. Despite the abundance of omics data and analysis techniques, researchers still struggle to identify biological findings that replicate across data sets and translate into clinical applications. In this dissertation, we employ combinatorial optimization techniques to improve upon three steps in the precision medicine analysis pipeline: 1) data cleaning, 2) community detection, and 3) feature …

Vertex Identification In Graphs, Yuya Kono

Dissertations

In recent decades, there has been increased interest in studying ways touniquely identify the vertices of a given graph. Two of best-known vertex identification methods are referred to as the metric dimension introduced by Slater and by Harary, and Melter in the1970s, and the partition dimension introduced by Chartrand in 2000. The first method deals with locating an ordered set of vertices in a connected graph G and uniquely identifying each vertex of G by means of the distance between this vertex and the vertices in the ordered set. The second method deals with partitioning the vertex set of a …

Multicolor Ramsey And List Ramsey Numbers For Double Stars, Jake Ruotolo

Honors Undergraduate Theses

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. For a graph H, the k-color Ramsey number r(H; k) of H is the smallest integer n such that every k-edge-coloring of K_n contains a monochromatic copy of H. Despite active research for decades, very little is known about Ramsey numbers of graphs. This is especially true for r(H; k) when k is at least 3, also known as the multicolor Ramsey number of …

Decisive Neutrality, Restricted Decisive Neutrality, And Split Decisive Neutrality On Median Semilattices And Median Graphs., Ulf Högnäs

Electronic Theses and Dissertations

Consensus functions on finite median semilattices and finite median graphs are studied from an axiomatic point of view. We start with a new axiomatic characterization of majority rule on a large class of median semilattices we call sufficient. A key axiom in this result is the restricted decisive neutrality condition. This condition is a restricted version of the more well-known axiom of decisive neutrality given in [4]. Our theorem is an extension of the main result given in [7]. Another main result is a complete characterization of the class of consensus on a finite median semilattice that satisfies the axioms …

Using Magic In Computing Education And Outreach, Ronald I. Greenberg, Dale F. Reed

Computer Science: Faculty Publications and Other Works

This special session explores the use of magic tricks based on computer science ideas; magic tricks help grab students' attention and can motivate them to invest more deeply in underlying CS concepts. Error detection ideas long used by computer scientists provide a particularly rich basis for working such "magic'', with a CS Unplugged parity check activity being a notable example. Prior work has shown that one can perform much more sophisticated tricks than the relatively well-known CS Unplugged activity, and these tricks can motivate analyses across a wide variety of computer science concepts and are relevant to learning objectives across …

A Weighted Möbius Function, Derek Garton

Mathematics and Statistics Faculty Publications and Presentations

Fix an odd prime ℓ and let G be the poset of isomorphism classes of finite abelian ℓ-groups, ordered by inclusion. If ξ:G→R^≥0 is a discrete probability distribution on G and A ∈ G, define the Ath moment of ξ to be . The question of determining conditions that ensure ξ is completely determined by its moments has been of recent interest in many problems of Cohen–Lenstra type. Furthermore, recovering ξ from its moments requires a new Möbius-type inversion formula on G. In this paper, we define this function, relate it to the classical Möbius …

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.

Automated Conjecturing Approach For Benzenoids, David Muncy

Theses and Dissertations

Benzenoids are graphs representing the carbon structure of molecules, defined by a closed path in the hexagonal lattice. These compounds are of interest to chemists studying existing and potential carbon structures. The goal of this study is to conjecture and prove relations between graph theoretic properties among benzenoids. First, we generate conjectures on upper bounds for the domination number in benzenoids using invariant-defined functions. This work is an extension of the ideas to be presented in a forthcoming paper. Next, we generate conjectures using property-defined functions. As the title indicates, the conjectures we prove are not thought of on our …

Combinatorial And Algebraic Coding Techniques For Flash Memory Storage, Kathryn A. Haymaker

Department of Mathematics: Dissertations, Theses, and Student Research

Error-correcting codes are used to achieve reliable and efficient transmission when storing or sending information across a noisy channel. This thesis investigates a mathematical approach to coding techniques for storage devices such as flash memory storage, although many of the resulting codes and coding schemes can be applied in other contexts. The main contributions of this work include the design of efficient codes and decoding algorithms using discrete structures such as graphs and finite geometries, and developing a variety of strategies for adapting codes to a multi-level setting.

Information storage devices are prone to errors over time, and the frequency …

Constructions And Enumeration Methods For Cubic Graphs And Trees, Erica R. Gilliland

Undergraduate Honors Thesis Collection

The goal of this thesis is to study two related problems that, in the broadest terms, lie in a branch of mathematics called graph theory. The first problem examines some new techniques for constructing a Hamilton graph of least possible order and having a preassigned girth, and the second concerns the enumeration of a certain type of graphs called trees.

An Algorithm To Generate Two-Dimensional Drawings Of Conway Algebraic Knots, Jen-Fu Tung

Masters Theses & Specialist Projects

The problem of finding an efficient algorithm to create a two-dimensional embedding of a knot diagram is not an easy one. Typically, knots with a large number of crossings will not nicely generate two-dimensional drawings. This thesis presents an efficient algorithm to generate a knot and to create a nice two-dimensional embedding of the knot. For the purpose of this thesis a drawing is “nice” if the number of tangles in the diagram consisting of half-twists is minimal. More specifically, the algorithm generates prime, alternating Conway algebraic knots in O(n) time where n is the number of crossings …

The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz

Faculty Publications & Research

Erdős and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

Discrete Mathematics With Proof Second Edition, Eric Gossett

Faculty Books

Discrete mathematics has become increasingly popular in recent years due to its growing applications in the field of computer science. Discrete Mathematics with Proof, Second Edition continues to facilitate an up-to-date understanding of this important topic, exposing readers to a wide range of modern and technological applications. The book begins with an introductory chapter that provides an accessible explanation of discrete mathematics. Subsequent chapters explore additional related topics including counting, finite probability theory, recursion, formal models in computer science, graph theory, trees, the concepts of functions, and relations.