Discrete Mathematics and Combinatorics Commons^™

Discrete Geometry And Covering Problems, Alexander Hsu

CMC Senior Theses

This thesis explores several problems in discrete geometry, focusing on covering problems. We first go over some well known results, explaining Keith Ball's solution to the symmetric Tarski plank problem, as well as results of Alon and F\"uredi on covering all but vertices of a cube with hyperplanes. The former extensively utilizes techniques from matrix analysis, and the latter applies polynomial method. We state and explore the related problem, asking for the number of parallel hyperplanes required to cover a given discrete set of points in $\mathbb{Z}^{d}$ whose entries are bounded, and prove that there exist sets which are ``difficult'' …

The Subconstituent Algebra Of A Hypercube, Jared B. Billet

UNF Graduate Theses and Dissertations

We study the hypercube and the associated subconstituent algebra. Let Q_D denote the hypercube with dimension D and let X denote the vertex set of Q_D. Fix a vertex x in X. We denote by A the adjacency matrix of Q_D and by A* = A*(x) the diagonal matrix with yy-entry equal to D − 2i, where i is the distance between x and y. The subconstitutent algebra T = T(x) of Q_D with respect to x is generated by A and A* . We show that A 2A* − 2AA*A + A*A 2 = 4A* A*2A − 2A*AA* + …

Algebraic And Geometric Properties Of Hierarchical Models, Aida Maraj

Theses and Dissertations--Mathematics

In this dissertation filtrations of ideals arising from hierarchical models in statistics related by a group action are are studied. These filtrations lead to ideals in polynomial rings in infinitely many variables, which require innovative tools. Regular languages and finite automata are used to prove and explicitly compute the rationality of some multivariate power series that record important quantitative information about the ideals. Some work regarding Markov bases for non-reducible models is shown, together with advances in the polyhedral geometry of binary hierarchical models.

Graph-Theoretic Simplicial Complexes, Hajos-Type Constructions, And K-Matchings, Julianne Vega

Theses and Dissertations--Mathematics

A graph property is monotone if it is closed under the removal of edges and vertices. Given a graph G and a monotone graph property P, one can associate to the pair (G,P) a simplicial complex, which serves as a way to encode graph properties within faces of a topological space. We study these graph-theoretic simplicial complexes using combinatorial and topological approaches as a way to inform our understanding of the graphs and their properties.

In this dissertation, we study two families of simplicial complexes: (1) neighborhood complexes and (2) k-matching complexes. A neighborhood complex is a simplicial …

Geometry Of Linear Subspace Arrangements With Connections To Matroid Theory, William Trok

Theses and Dissertations--Mathematics

This dissertation is devoted to the study of the geometric properties of subspace configurations, with an emphasis on configurations of points. One distinguishing feature is the widespread use of techniques from Matroid Theory and Combinatorial Optimization. In part we generalize a theorem of Edmond's about partitions of matroids in independent subsets. We then apply this to establish a conjectured bound on the Castelnuovo-Mumford regularity of a set of fat points.

We then study how the dimension of an ideal of point changes when intersected with a generic fat subspace. In particular we introduce the concept of a ``very unexpected hypersurface'' …

Uniform Three-Class Regular Partial Steiner Triple Systems With Uniform Degrees, Prangya Rani Parida

Dissertations, Master's Theses and Master's Reports

A Partial Steiner Triple system (X, T) is a finite set of points C and a collection T of 3-element subsets of C that every pair of points intersect in at most 1 triple. A 3-class regular PSTS (3-PSTS) is a PSTS where the points can be partitioned into 3 classes (each class having size m, n and p respectively) such that no triple belongs to any class and any two points from the same class occur in the same number of triples (a, b and c respectively). The 3-PSTS is said to be uniform if m = n = …

Phylogenetic Networks And Functions That Relate Them, Drew Scalzo

Williams Honors College, Honors Research Projects

Phylogenetic Networks are defined to be simple connected graphs with exactly n labeled nodes of degree one, called leaves, and where all other unlabeled nodes have a degree of at least three. These structures assist us with analyzing ancestral history, and its close relative - phylogenetic trees - garner the same visualization, but without the graph being forced to be connected. In this paper, we examine the various characteristics of Phylogenetic Networks and functions that take these networks as inputs, and convert them to more complex or simpler structures. Furthermore, we look at the nature of functions as they relate …

Interval Valued Neutrosophic Shortest Path Problem By A* Algorithm, Florentin Smarandache, S. Khrisna Prabha, Said Broumi

Branch Mathematics and Statistics Faculty and Staff Publications

Many researchers have been proposing various algorithms to unravel different types of fuzzy shortest path problems. There are many algorithms like Dijkstra’s, Bellman-Ford,Floyd-Warshall and kruskal’s etc are existing for solving the shortest path problems. In this work a shortest path problem with interval valued neutrosophic numbers is investigated using the proposed algorithm. A* algorithm is extensively applied in pathfinding and graph traversal.Unlike the other algorithms mentioned above, A* algorithm entails heuristic function to uncover the cost of path that traverses through the particular state. In the structured work A* algorithm is applied to unravel the length of the shortest path …

On Eigenvalue Bounds For The Finite-State Birth-Death Process Intensity Matrix, R.R.P Tan, K Ikeda, Len Patrick Dominic M. Garces

Mathematics Faculty Publications

The paper sets forth a novel eigenvalue interlacing property across the finite-state birth-death process intensity matrix and two clearly identified submatrices as an extension of Cauchy’s interlace theorem for Hermitian matrix eigenvalues. A supplemental proof involving an examination of probabilities acquired from specific movements across states and a derivation of a form for the eigenpolynomial of the matrix through convolution and Laplace transform is then presented towards uncovering a similar characteristic for the general Markov chain transition rate matrix. Consequently, the proposition generates bounds for each eigenvalue of the original matrix, easing numerical computation. To conclude, the applicability of the …

On The Ranks Of String C-Group Representations For Symplectic And Orthogonal Groups, Peter A. Brooksbank

Faculty Journal Articles

We determine the ranks of string C-group representations of 4-dimensional projective symplectic groups over a finite field, and comment on those of higher-dimensional symplectic and orthogonal groups.

Orthogonal Groups In Characteristic 2 Acting On Polytopes Of High Rank, Peter A. Brooksbank, Dimitri Leemans, John T. Ferrara

Faculty Journal Articles

No abstract provided.

Maximality And Applications Of Subword-Closed Languages, Rhys Davis Jones

UNF Graduate Theses and Dissertations

Characterizing languages D that are maximal with the property that D^* ⊆ S^⊗ is an important problem in formal language theory with applications to coding theory and DNA codewords. Given a finite set of words of a fixed length S, the constraint, we consider its subword closure, S^⊗, the set of words whose subwords of that fixed length are all in the constraint. We investigate these maximal languages and present characterizations for them. These characterizations use strongly connected components of deterministic finite automata and lead to polynomial time algorithms for generating such languages. We prove that …

A Mathematical Analysis Of The Game Of Santorini, Carson Clyde Geissler

Senior Independent Study Theses

Santorini is a two player combinatorial board game. Santorini bears resemblance to the graph theory game of Geography, a game of moving and deleting vertices on a graph. We explore Santorini with game theory, complexity theory, and artificial intelligence. We present David Lichtenstein’s proof that Geography is PSPACE-hard and adapt the proof for generalized forms of Santorini. Last, we discuss the development of an AI built for a software implementation of Santorini and present a number of improvements to that AI.

Cycle Double Covers And Integer Flows, Zhang Zhang

Graduate Theses, Dissertations, and Problem Reports (ETD)

My research focuses on two famous problems in graph theory, namely the cycle double cover conjecture and the integer flows conjectures. This kind of problem is undoubtedly one of the major catalysts in the tremendous development of graph theory. It was observed by Tutte that the Four color problem can be formulated in terms of integer flows, as well as cycle covers. Since then, the topics of integer flows and cycle covers have always been in the main line of graph theory research. This dissertation provides several partial results on these two classes of problems.

Weighted Modulo Orientations Of Graphs, Jianbing Liu

Graduate Theses, Dissertations, and Problem Reports (ETD)

This dissertation focuses on the subject of nowhere-zero flow problems on graphs. Tutte's 5-Flow Conjecture (1954) states that every bridgeless graph admits a nowhere-zero 5-flow, and Tutte's 3-Flow Conjecture (1972) states that every 4-edge-connected graph admits a nowhere-zero 3-flow. Extending Tutte's flows conjectures, Jaeger's Circular Flow Conjecture (1981) says every 4k-edge-connected graph admits a modulo (2k+1)-orientation, that is, an orientation such that the indegree is congruent to outdegree modulo (2k+1) at every vertex. Note that the k=1 case of Circular Flow Conjecture coincides with the 3-Flow Conjecture, and the case of k=2 implies the 5-Flow Conjecture. This work is devoted …

Circuits And Cycles In Graphs And Matroids, Yang Wu

Graduate Theses, Dissertations, and Problem Reports (ETD)

This dissertation mainly focuses on characterizing cycles and circuits in graphs, line graphs and matroids. We obtain the following advances.

1. Results in graphs and line graphs. For a connected graph G not isomorphic to a path, a cycle or a K1,3, let pc(G) denote the smallest integer n such that the nth iterated line graph Ln(G) is panconnected. A path P is a divalent path of G if the internal vertices of P are of degree 2 in G. If every edge of P is a cut edge of G, then P is a bridge divalent path of G; …

Model Selection And Experimental Design Of Biological Networks With Algebraic Geometry, Anyu Zhang

Mathematics Theses and Dissertations

Model selection based on experimental data is an essential challenge in biological data science. In decades, the volume of biological data from varied sources, including laboratory experiments, field observations, and patient health records has seen an unprecedented increase. Mainly when collecting data is expensive or time-consuming, as it is often in the case with clinical trials and biomolecular experiments, the problem of selecting information-rich data becomes crucial for creating relevant models.

Motivated by certain geometric relationships between data, we partitioned input data sets, especially data sets that correspond to a unique basis, into equivalence classes with the same basis to …

Rearrangement Operations On Unrooted Phylogenetic Networks, Remie Janssen, Jonathan Klawitter

Theory & Applications of Graphs

Rearrangement operations transform a phylogenetic tree into another one and hence induce a metric on the space of phylogenetic trees. Popular operations for unrooted phylogenetic trees are NNI (nearest neighbour interchange), SPR (subtree prune and regraft), and TBR (tree bisection and reconnection). Recently, these operations have been extended to unrooted phylogenetic networks, which are generalisations of phylogenetic trees that can model reticulated evolutionary relationships. Here, we study global and local properties of spaces of phylogenetic networks under these three operations. In particular, we prove connectedness and asymptotic bounds on the diameters of spaces of different classes of phylogenetic networks, including …

Q-Sumudu Transforms Pertaining To The Product Of Family Of Q-Polynomials And Generalized Basic Hypergeometric Functions, V. K. Vyas, Ali A. Al –Jarrah, S. D. Purohit

Applications and Applied Mathematics: An International Journal (AAM)

The prime objective of commenced article is to determine q-Sumudu transforms of a product of unified family of q-polynomials with basic (or q-) analog of Fox’s H-function and q-analog of I-functions. Specialized cases of the leading outcome are further evaluated as q-Sumudu transform of general class of q-polynomials and q-Sumudu transforms of the basic analogs of Fox’s H-function and I-functions.

Adjoint Appell-Euler And First Kind Appell-Bernoulli Polynomials, Pierpaolo Natalini, Paolo E. Ricci

Applications and Applied Mathematics: An International Journal (AAM)

The adjunction property, recently introduced for Sheffer polynomial sets, is considered in the case of Appell polynomials. The particular case of adjoint Appell-Euler and Appell-Bernoulli polynomials of the first kind is analyzed.