Discrete Mathematics and Combinatorics Commons^™

Modeling Stochastically Intransitive Relationships In Paired Comparison Data, Ryan Patrick Alexander Mcshane

Statistical Science Theses and Dissertations

If the Warriors beat the Rockets and the Rockets beat the Spurs, does that mean that the Warriors are better than the Spurs? Sophisticated fans would argue that the Warriors are better by the transitive property, but could Spurs fans make a legitimate argument that their team is better despite this chain of evidence?

We first explore the nature of intransitive (rock-scissors-paper) relationships with a graph theoretic approach to the method of paired comparisons framework popularized by Kendall and Smith (1940). Then, we focus on the setting where all pairs of items, teams, players, or objects have been compared to …

Special Subset Vertex Multisubgraphs For Multi Networks, Florentin Smarandache, W.B. Vasantha Kandasamy, Ilanthenral K

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors study special type of subset vertex multi subgraphs; these multi subgraphs can be directed or otherwise. Another special feature of these subset vertex multigraphs is that we are aware of the elements in each vertex set and how it affects the structure of both subset vertex multisubgraphs and edge multisubgraphs. It is pertinent to record at this juncture that certain ego centric directed multistar graphs become empty on the removal of one edge, there by theorising the importance, and giving certain postulates how to safely form ego centric multi networks. Given any subset vertex multigraph we …

Lattice Simplices: Sufficiently Complicated, Brian Davis

Theses and Dissertations--Mathematics

Simplices are the "simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields.

In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincar\'e series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of …

Revisiting The Isoperimetric Graph Partitioning Problem, Sravan Danda, Aditya Challa, B. S. Daya Sagar, Laurent Najman

Journal Articles

Isoperimetric graph partitioning, which is also known as the Cheeger cut, is NP-hard in its original form. In the literature, multiple modifications to this problem have been proposed to obtain approximation algorithms for clustering applications. In the context of image segmentation, a heuristic continuous relaxation to this problem introduced by Leo Grady and Eric L. Schwartz has yielded good quality results. This algorithm is based on solving a linear system of equations involving the Laplacian of the image graph. Furthermore, the same algorithm applied to a maximum spanning tree (MST) of the image graph was shown to produce similar results …

Positivity Among P-Partition Generating Functions Of Partially Ordered Sets, Nate Lesnevich

Honors Theses

We find necessary and separate sufficient conditions for the difference between two labeled partially ordered set's (poset) partition generating functions to be positive in the fundamental basis. We define the notion of a jump sequence for a poset and show how different conditions on the jump sequences of two posets are necessary for those posets to have an order relation in the fundamental basis. Our sufficient conditions are of two types. First, we show how manipulating a poset's Hasse diagram produces a poset that is greater according to the fundamental basis. Secondly, we also provide tools to explain posets that …

Some Results On Partial Difference Sets And Partial Geometries, Eric J. Neubert Jr

Dissertations, Master's Theses and Master's Reports

This thesis shows results on 3 different problems involving partial difference sets (PDS) in abelian groups, and uses PDS to study partial geometries with an abelian Singer group. First, the last two undetermined cases of PDS on abelian groups with k ≤ 100, both of order 216, were shown not to exist. Second, new parameter bounds for k and ∆ were found for PDS on abelian groups of order p^n , p an odd prime, n odd. A parameter search on p^5 in particular was conducted, and only 5 possible such cases remain for p < 250. Lastly, the existence of rigid type partial geometries with an abelian Singer group are examined; existence is left undetermined for 11 cases with α ≤ 200. This final study led to the determination of nonexistence for an infinite class of cases which impose a negative Latin type PDS.

Neutrosophic Triplet Structures - Vol. 1, Florentin Smarandache, Memet Sahin

Branch Mathematics and Statistics Faculty and Staff Publications

Neutrosophic set has been derived from a new branch of philosophy, namely Neutrosophy. Neutrosophic set is capable of dealing with uncertainty, indeterminacy and inconsistent information. Neutrosophic set approaches are suitable to modeling problems with uncertainty, indeterminacy and inconsistent information in which human knowledge is necessary, and human evaluation is needed. Neutrosophic set theory was firstly proposed in 1998 by Florentin Smarandache, who also developed the concept of single valued neutrosophic set, oriented towards real world scientific and engineering applications. Since then, the single valued neutrosophic set theory has been extensively studied in books and monographs, the properties of neutrosophic sets …

Gallai-Ramsey Number For Classes Of Brooms, Benjamin J. Hamlin

College of Graduate Studies: Theses & Dissertations

Given a graph $G$, we consider the problem of finding the minimum number $n$ such that any $k$ edge colored complete graph on $n$ vertices contains either a rainbow colored triangle or a monochromatic copy of the graph $G$, denoted $gr_k(K_{3}:G)$. More precisely we consider $G=B_{m,\ell}$ where $B_{m,\ell}$ is a broom graph with $m$ representing the number of vertices on the handle and $\ell$ representing the number of bristle vertices. We develop a technique to reduce the difficulty of finding $gr_{k}(K_{3}:B_{m,\ell})$, and use the technique to prove a few cases with a fixed handle length, but arbitrarily many bristles. Further, …

Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier

College of Graduate Studies: Theses & Dissertations

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound …

Taking A Canon To The Adjunction Formula, Paul M. Harrelson

College of Graduate Studies: Theses & Dissertations

In this paper, we show how the canonical divisor of a graph is related to the canonical divisor of its subgraph. The use of chip firing and the adjunction formula for graphs ex- plains said relation and even completes it. We go on to show the difference between the formula for full subgraphs and that of non-full subgraphs. Examples are used to simplify these results and to see the adjunction formula in action. Finally, we show that though the adjunction formula seems simple at first glance, it is somewhat complex and rather useful.

Inverse Problems Related To The Wiener And Steiner-Wiener Indices, Matthew Gentry

College of Graduate Studies: Theses & Dissertations

In a graph, the generalized distance between multiple vertices is the minimum number of edges in a connected subgraph that contains these vertices. When we consider such distances between all subsets of $k$ vertices and take the sum, it is called the Steiner $k$-Wiener index and has important applications in Chemical Graph Theory. In this thesis we consider the inverse problems related to the Steiner Wiener index, i.e. for what positive integers is there a graph with Steiner Wiener index of that value?

Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, Katherine M. Horacek

Graduate Theses, Dissertations, and Problem Reports (ETD)

In my dissertation, I present results on two types of edge coloring problems for graphs.

For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with characteristic χ(Σ) ≤ 0, it is known ∆(Σ) ≥ H(χ(Σ))−1, where H(χ(Σ)) is the Heawood number of the surface, and if the Euler char- acteristic χ(Σ) ∈ {−7, −6, . . . , −1, 0}, ∆(Σ) is already …

Infinite Matroids And Transfinite Sequences, Martin Andrew Storm

Graduate Theses, Dissertations, and Problem Reports (ETD)

A matroid is a pair M = (E,I) where E is a set and I is a set of subsets of E that are called independent, echoing the notion of linear independence. One of the leading open problems in infinite matroid theory is the Matroid Intersection Conjecture by Nash-Williams which is a generalization of Hall’s Theorem. In [31] Jerzy Wojciechowski introduced µ- admissibility for pairs of matroids on the same ground set and showed that it is a necessary condition for the existence of a matching. A pair of matroids (M,W) with common ground set E is µ-admissible if a …

Subsets Of Vertices Of The Same Size And The Same Maximum Distance, Maria Axenovich, Dominik Duerrschnabel

Theory & Applications of Graphs

For a simple connected graph G=(V,E) and a subset X of its vertices, let

d*(X) = max {dist}_G(x,y): x,y ∈ X}

and let h*(G) be the largest k such that there are disjoint vertex subsets A and B of G, each of size k such that d*(A) = d*(B). Let h*(n) = min {h*(G): |V(G)|=n}. We prove that h*(n) =⌊(n+1)/3 ⌋, for n ≥ 6. This solves the homometric set problem restricted to the largest distance exactly. In addition we compare h*(G) with a respective function h_diam(G), where …

Simplifying Coefficients In A Family Of Ordinary Differential Equations Related To The Generating Function Of The Laguerre Polynomials, Feng Qi

Applications and Applied Mathematics: An International Journal (AAM)

In the paper, by virtue of the Faà di Bruno formula, properties of the Bell polynomials of the second kind, and the Lah inversion formula, the author simplifies coefficients in a family of ordinary differential equations related to the generating function of the Laguerre polynomials.

Italian Domination On Ladders And Related Products, Bradley Gardner

Electronic Theses and Dissertations

An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete graph $K_2$. We will find the value of the Italian domination …

Finite Simple Graphs And Their Associated Graph Lattices, James B. Hart, Brian Frazier

Theory & Applications of Graphs

In his 2005 dissertation, Antoine Vella explored combinatorical aspects of finite graphs utilizing a topological space whose open sets are intimately tied to the structure of the graph. In this paper, we go a step further and examine some aspects of the open set lattices induced by these topological spaces. In particular, we will characterize all lattices that constitute the opens for finite simple graphs endowed with this topology, explore the structure of these lattices, and show that these lattices contain information necessary to reconstruct the graph and its complement in several ways.

A Proof Of The "Magicness" Of The Siam Construction Of A Magic Square, Joshua Arroyo

Rose-Hulman Undergraduate Mathematics Journal

A magic square is an n x n array filled with n² distinct positive integers 1, 2, ..., n² such that the sum of the n integers in each row, column, and each of the main diagonals are the same. A Latin square is an n x n array consisting of n distinct symbols such that each symbol appears exactly once in each row and column of the square. Many articles dealing with the construction of magic squares introduce the Siam method as a "simple'' construction for magic squares. Rarely, however, does the article actually prove that the …

On Orders Of Elliptic Curves Over Finite Fields, Yujin H. Kim, Jackson Bahr, Eric Neyman, Gregory Taylor

Rose-Hulman Undergraduate Mathematics Journal

In this work, we completely characterize by $j$-invariant the number of orders of elliptic curves over all finite fields $F_{p^r}$ using combinatorial arguments and elementary number theory. Whenever possible, we state and prove exactly which orders can be taken on.

Transformations On Double Occurrence Words Motivated By Dna Rearrangement, Daniel Cruz, Margherita Maria Ferrari, Lukas Nabergall, Natasa Jonoska, Masahico Saito

Annual Symposium on Biomathematics and Ecology Education and Research

No abstract provided.