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

Discrete Mathematics and Combinatorics Commons

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

687 Full-Text Articles 842 Authors 64092 Downloads 75 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

687 full-text articles. Page 1 of 23.

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


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


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


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


Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica McDonald 2017 Middle Georgia State University

Application Of An Extremal Result Of Erdős And Gallai To The (N,K,T) Problem, Matt Noble, Peter Johnson, Dean Hoffman, Jessica Mcdonald

Theory and Applications of Graphs

An extremal result about vertex covers, attributed by Hajnal to Erdős and Gallai, is applied to prove the following: If n, k, and t are integers satisfying n ≥ k ≥ t ≥ 3 and k ≤ 2t - 2, and G is a graph with the minimum number of edges among graphs on n vertices with the property that every induced subgraph on k vertices contains a complete subgraph on t vertices, then every component of G is complete.


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


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.


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


Orthogonal Representations, Projective Rank, And Fractional Minimum Positive Semidefinite Rank: Connections And New Directions, Leslie Hogben, Kevin F. Palmowski, David E. Roberson, Simone Severini 2017 Iowa State University

Orthogonal Representations, Projective Rank, And Fractional Minimum Positive Semidefinite Rank: Connections And New Directions, Leslie Hogben, Kevin F. Palmowski, David E. Roberson, Simone Severini

Electronic Journal of Linear Algebra

Fractional minimum positive semidefinite rank is defined from r-fold faithful orthogonal representations and it is shown that the projective rank of any graph equals the fractional minimum positive semidefinite rank of its complement. An r-fold version of the traditional definition of minimum positive semidefinite rank of a graph using Hermitian matrices that fit the graph is also presented. This paper also introduces r-fold orthogonal representations of graphs and formalizes the understanding of projective rank as fractional orthogonal rank. Connections of these concepts to quantum theory, including Tsirelson's problem, are discussed.


Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb 2017 University of Haifa-Oranim

Two Short Proofs Of The Perfect Forest Theorem, Yair Caro, Josef Lauri, Christina Zarb

Theory and Applications of Graphs

A perfect forest is a spanning forest of a connected graph $G$, all of whose components are induced subgraphs of $G$ and such that all vertices have odd degree in the forest. A perfect forest generalised a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra.

We give here two very short proofs of the Perfect Forest Theorem which use only elementary notions from graph theory. Both our proofs ...


From Simplest Recursion To The Recursion Of Generalizations Of Cross Polytope Numbers, Yutong Yang 2017 Kennesaw State University

From Simplest Recursion To The Recursion Of Generalizations Of Cross Polytope Numbers, Yutong Yang

Honors College Capstones and Theses

My research project involves investigations in the mathematical field of combinatorics. The research study will be based on the results of Professors Steven Edwards and William Griffiths, who recently found a new formula for the cross-polytope numbers. My topic will be focused on "Generalizations of cross-polytope numbers". It will include the proofs of the combinatorics results in Dr. Edwards and Dr. Griffiths' recently published paper. $E(n,m)$ and $O(n,m)$, the even terms and odd terms for Dr. Edward's original combinatorial expression, are two distinct combinatorial expressions that are in fact equal. But there is no obvious ...


Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green 2017 East Tennessee State University

Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green

Electronic Theses and Dissertations

To determine the function of a protein, we must know its 3-dimensional structure, which can be difficult to ascertain. Currently, predictive models are used to determine the structure of a protein from its sequence, but these models do not always predict the correct structure. To this end we use a nested graph model along with weighted invariants to minimize the errors and improve the accuracy of a predictive model to determine if we have the correct structure for a protein.


On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy 2017 East Tennessee State University

On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy

Electronic Theses and Dissertations

For a graph G = (V;E), a pebble distribution is defined as a mapping of the vertex set in to the integers, where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling distribution f if there exists some sequence of rubbling and pebbling moves that places a pebble on x. A pebbling distribution where ...


"Returning To The Root" Of The Problem: Improving The Social Condition Of African Americans Through Science And Mathematics Education, Vanessa R. Pitts Bannister, Julius Davis, Jomo Mutegi, LaTasha Thompson, Deborah Lewis 2017 Florida A&M University

"Returning To The Root" Of The Problem: Improving The Social Condition Of African Americans Through Science And Mathematics Education, Vanessa R. Pitts Bannister, Julius Davis, Jomo Mutegi, Latasha Thompson, Deborah Lewis

Catalyst: A Social Justice Forum

The underachievement and underrepresentation of African Americans in STEM (Science, Technology, Engineering and Mathematics) disciplines have been well documented. Efforts to improve the STEM education of African Americans continue to focus on relationships between teaching and learning and factors such as culture, race, power, class, learning preferences, cultural styles and language. Although this body of literature is deemed valuable, it fails to help STEM teacher educators and teachers critically assess other important factors such as pedagogy and curriculum. In this article, the authors argue that both pedagogy and curriculum should be centered on the social condition of African Americans – thus ...


Digital Commons powered by bepress