Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

705 Full-Text Articles 858 Authors 65381 Downloads 77 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

705 full-text articles. Page 1 of 24.

An Extended Formulation Of The Convex Recoloring Problem On A Phylogenetic Tree, Sangho Shim 2017 Illinois State University

An Extended Formulation Of The Convex Recoloring Problem On A Phylogenetic Tree, Sangho Shim

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Repeat And Return Patterns In Double Occurrence Words, Lukas Nabergall 2017 University of South Florida

Repeat And Return Patterns In Double Occurrence Words, Lukas Nabergall

Annual Symposium on Biomathematics and Ecology: Education and Research

No abstract provided.


Some Results In Combinatorial Number Theory, Karl Levy 2017 The Graduate Center, City University of New York

Some Results In Combinatorial Number Theory, Karl Levy

All Graduate Works by Year: Dissertations, Theses, and Capstone Projects

The first chapter establishes results concerning equidistributed sequences of numbers. For a given $d\in\mathbb{N}$, $s(d)$ is the largest $N\in\mathbb{N}$ for which there is an $N$-regular sequence with $d$ irregularities. We compute lower bounds for $s(d)$ for $d\leq 10000$ and then demonstrate lower and upper bounds $\left\lfloor\sqrt{4d+895}+1\right\rfloor\leq s(d)< 24801d^{3} + 942d^{2} + 3$ for all $d\geq 1$. In the second chapter we ask if $Q(x)\in\mathbb{R}[x]$ is a degree $d$ polynomial such that for $x\in[x_k]=\{x_1,\cdots,x_k\}$ we have $|Q(x)|\leq 1$, then how big can its lead coefficient be? We prove that there is a unique polynomial, which we call $L_{d,[x_k]}(x)$, with maximum lead coefficient under these constraints and construct an algorithm that generates $L_{d,[x_k]}(x)$.


A Weighted Möbius Function, Derek Garton 2017 Portland State University

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 function ...


Refined Inertia Of Matrix Patterns, Kevin N. Vander Meulen, Jonathan Earl, Adam Van Tuyl 2017 Redeemer University College

Refined Inertia Of Matrix Patterns, Kevin N. Vander Meulen, Jonathan Earl, Adam Van Tuyl

Electronic Journal of Linear Algebra

This paper explores how the combinatorial arrangement of prescribed zeros in a matrix affects the possible eigenvalues that the matrix can obtain. It demonstrates that there are inertially arbitrary patterns having a digraph with no 2-cycle, unlike what happens for nonzero patterns. A class of patterns is developed that are refined inertially arbitrary but not spectrally arbitrary, making use of the property of a properly signed nest. The paper includes a characterization of the inertially arbitrary and refined inertially arbitrary patterns of order three, as well as the patterns of order four with the least number of nonzero entries.


Spectral Bound For Separations In Eulerian Digraphs, Krystal Guo 2017 University of Waterloo

Spectral Bound For Separations In Eulerian Digraphs, Krystal Guo

Electronic Journal of Linear Algebra

The spectra of digraphs, unlike those of graphs, is a relatively unexplored territory. In a digraph, a separation is a pair of sets of vertices D and Y such that there are no arcs from D and Y. For a subclass of Eulerian digraphs, a bound on the size of a separation is obtained in terms of the eigenvalues of the Laplacian matrix. An infinite family of tournaments, namely, the Paley digraphs, where the bound holds with equality, is also given.


The Enhanced Principal Rank Characteristic Sequence Over A Field Of Characteristic 2, Xavier Martínez-Rivera 2017 Iowa State University

The Enhanced Principal Rank Characteristic Sequence Over A Field Of Characteristic 2, Xavier Martínez-Rivera

Electronic Journal of Linear Algebra

The enhanced principal rank characteristic sequence (epr-sequence) of an $n \times n$ symmetric matrix over a field $\F$ was recently defined as $\ell_1 \ell_2 \cdots \ell_n$, where $\ell_k$ is either $\tt A$, $\tt S$, or $\tt N$ based on whether all, some (but not all), or none of the order-$k$ principal minors of the matrix are nonzero. Here, a complete characterization of the epr-sequences that are attainable by symmetric matrices over the field $\Z_2$, the integers modulo $2$, is established. Contrary to the attainable epr-sequences over a field of characteristic $0$, this characterization reveals that the attainable epr-sequences over ...


Efficiently Representing The Integer Factorization Problem Using Binary Decision Diagrams, David Skidmore 2017 Utah State University

Efficiently Representing The Integer Factorization Problem Using Binary Decision Diagrams, David Skidmore

All Graduate Plan B and other Reports

Let p be a prime positive integer and let α be a positive integer greater than 1. A method is given to reduce the problem of finding a nontrivial factorization of α to the problem of finding a solution to a system of modulo p polynomial congruences where each variable in the system is constrained to the set {0,...,p − 1}. In the case that p = 2 it is shown that each polynomial in the system can be represented by an ordered binary decision diagram with size less than 20.25log2(α)3 + 16.5log2(α)2 + 6log ...


Antichains And Diameters Of Set Systems, Brent McKain 2017 University of Nebraska-Lincoln

Antichains And Diameters Of Set Systems, Brent Mckain

Dissertations, Theses, and Student Research Papers in Mathematics

In this thesis, we present a number of results, mostly concerning set systems that are antichains and/or have bounded diameter. Chapter 1 gives a more detailed outline of the thesis. In Chapter 2, we give a new short proof of Kleitman's theorem concerning the maximal size of a set system with bounded diameter. In Chapter 3, we turn our attention to antichains with bounded diameter. Šileikis conjectured that an antichain of diameter D has size at most (n/D/2). We present several partial results towards the conjecture.

In 2014, Leader and Long gave asymptotic bounds on the ...


Vertex Weighted Spectral Clustering, Mohammad Masum 2017 East Tennessee State University

Vertex Weighted Spectral Clustering, Mohammad Masum

Electronic Theses and Dissertations

Spectral clustering is often used to partition a data set into a specified number of clusters. Both the unweighted and the vertex-weighted approaches use eigenvectors of the Laplacian matrix of a graph. Our focus is on using vertex-weighted methods to refine clustering of observations. An eigenvector corresponding with the second smallest eigenvalue of the Laplacian matrix of a graph is called a Fiedler vector. Coefficients of a Fiedler vector are used to partition vertices of a given graph into two clusters. A vertex of a graph is classified as unassociated if the Fiedler coefficient of the vertex is close to ...


Inverses Of Bicyclic Graphs, SWARUP KUMAR PANDA 2017 ISI Delhi

Inverses Of Bicyclic Graphs, Swarup Kumar Panda

Electronic Journal of Linear Algebra

A graph G is said to be nonsingular (resp., singular) if its adjacency matrix A(G) is nonsingular (resp., singular). The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A(G) via a diagonal matrix of ±1s. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. In [C.D. Godsil. Inverses of trees. Combinatorica, 5(1):33–39, 1985.], Godsil proved that such graphs are invertible. He posed the question of characterizing the ...


Behavior Of Petrie Lines In Certain Edge-Transitive Graphs, Ruby A. Chick 2017 University of Texas at Tyler

Behavior Of Petrie Lines In Certain Edge-Transitive Graphs, Ruby A. Chick

Math Theses

We survey the construction and classification of one-, two- and infinitely-ended members of a class of highly symmetric, highly connected infinite graphs. In addition, we pose a conjecture concerning the relationship between the Petrie lines and ends of some infinitely-ended members of this class.


Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg 2017 Loyola University Chicago

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.


Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben 2017 Iowa State University

Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben

Namrata Vaswani

This paper studies the recursive robust principal components analysis problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low-dimensional subspace that is either fixed or changes slowly enough. A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above ...


Rainbow Copies Of C4 In Edge-Colored Hypercubes, József Balogh, Michelle Delcourt, Bernard Lidický, Cory Palmer 2017 University of Illinois at Urbana-Champaign

Rainbow Copies Of C4 In Edge-Colored Hypercubes, József Balogh, Michelle Delcourt, Bernard Lidický, Cory Palmer

Bernard Lidický

For positive integers k and d such that 4≤k4in a k-edge-coloring of the d-dimensional hypercube Qd. Interestingly, the k-edge-colorings of Qd yielding the maximum number of rainbow copies of C4 also have the property that every copy of C4 which is not rainbow is monochromatic.


On The Tree Search Problem With Non-Uniform Costs, Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyid, Tomáš Valla 2017 University of Verona

On The Tree Search Problem With Non-Uniform Costs, Ferdinando Cicalese, Balázs Keszegh, Bernard Lidický, Dömötör Pálvölgyid, Tomáš Valla

Bernard Lidický

Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T−e containing the vertex sought for, while incurring some known cost c(e). The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy ...


On Crossing Numbers Of Complete Tripartite And Balanced Complete Multipartite Graphs, Ellen Gethner, Leslie Hogben, Bernard Lidicky, Florian Pfender, Amanda Ruiz, Michael Young 2017 University of Colorado, Denver

On Crossing Numbers Of Complete Tripartite And Balanced Complete Multipartite Graphs, Ellen Gethner, Leslie Hogben, Bernard Lidicky, Florian Pfender, Amanda Ruiz, Michael Young

Bernard Lidický

The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of Gwith edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound . to . and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph ...


A Transformation That Preserves Principal Minors Of Skew-Symmetric Matrices, Abderrahim BOUSSAIRI, Brahim CHERGUI 2017 Faculté des Sciences Ain chock

A Transformation That Preserves Principal Minors Of Skew-Symmetric Matrices, Abderrahim Boussairi, Brahim Chergui

Electronic Journal of Linear Algebra

It is well known that two $n\times n$ symmetric matrices have equal corresponding principal minors of all orders if and only if they are diagonally similar. This result cannot be extended to arbitrary matrices. The aim of this work is to give a new transformation that preserves principal minors of skew-symmetric matrices.


Explorations Into Monomer-Dimer Tilings Of Planar Regions, Zachary Hall 2017 University of Wyoming

Explorations Into Monomer-Dimer Tilings Of Planar Regions, Zachary Hall

Honors Theses AY 16/17

The properties of monomer-dimer tilings of planar regions has been a focused area of study in the mathematical community for many years. Applications include areas such as diatomic molecular bonding and ice-formation. As my research has gone forth, discoveries have been made regarding the number of monomer-dimer tilings in specific regions. We also were able to characterize these larger tilings with polynomials that have not been published by others. Using mathematical programming, I have also found the probability distribution of where monomers will land in a completely random tiling of these square regions. Thorough research has also been done on ...


Turán Numbers Of Vertex-Disjoint Cliques In R-Partite Graphs, Anna Schenfisch 2017 University of Wyoming

Turán Numbers Of Vertex-Disjoint Cliques In R-Partite Graphs, Anna Schenfisch

Honors Theses AY 16/17

In a broad sense, graph theory has always been present in civilization. Graph theory is the math of connections - at a party, who knows each other? How many handshakes will each person in a meeting have to give before shaking hands with everyone? What is the best way to route traffic through a city's network of roads?

Extremal graph theory is a branch that deals with counting items (called vertices) and connections between two items (called edges) and determining the maximum/minimum number of characteristics needed to satisfy a certain property.

The specific topic of this paper is Turán ...


Digital Commons powered by bepress