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

Discrete Mathematics and Combinatorics Commons

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

712 Full-Text Articles 834 Authors 54052 Downloads 74 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

712 full-text articles. Page 1 of 24.

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


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


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


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


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


Does Logic Help Us Beat Monty Hall?, Adam J. Hammett, Nathan A. Harold, Tucker R. Rhodes 2017 Cedarville University

Does Logic Help Us Beat Monty Hall?, Adam J. Hammett, Nathan A. Harold, Tucker R. Rhodes

The Research and Scholarship Symposium

The classical Monty Hall problem entails that a hypothetical game show contestant be presented three doors and told that behind one door is a car and behind the other two are far less appealing prizes, like goats. The contestant then picks a door, and the host (Monty) is to open a different door which contains one of the bad prizes. At this point in the game, the contestant is given the option of keeping the door she chose or changing her selection to the remaining door (since one has already been opened by Monty), after which Monty opens the chosen ...


Six Septembers: Mathematics For The Humanist, Patrick Juola, Stephen Ramsay 2017 Duquesne University

Six Septembers: Mathematics For The Humanist, Patrick Juola, Stephen Ramsay

Zea E-Books

Scholars of all stripes are turning their attention to materials that represent enormous opportunities for the future of humanistic inquiry. The purpose of this book is to impart the concepts that underlie the mathematics they are likely to encounter and to unfold the notation in a way that removes that particular barrier completely. This book is a primer for developing the skills to enable humanist scholars to address complicated technical material with confidence. This book, to put it plainly, is concerned with the things that the author of a technical article knows, but isn’t saying. Like any field, mathematics ...


Involutions And Total Orthogonality In Some Finite Classical Groups, Gregory K. Taylor 2017 College of William and Mary

Involutions And Total Orthogonality In Some Finite Classical Groups, Gregory K. Taylor

Undergraduate Honors Theses

A group $G$ is called \emph{real} if every element is conjugate to its inverse, and $G$ is \emph{strongly real} if each of the conjugating elements may be chosen to be an involution, an element in $G$ which squares to the identity. Real groups are called as such because every irreducible character of a real group is real valued. A group $G$ is called \emph{totally orthogonal} if every irreducible complex representation is realizable over the field of real numbers. Total orthogonality is sufficient, but not necessary for reality.

Reality of representations is quantified in the Frobenius-Schur indicator. For ...


Minimum Rank Of Skew-Symmetric Matrices Described By A Graph, Mary Allison, Elizabeth Bodine, Luz Maria DeAlba, Joyati Debnath, Laura DeLoss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader, Amy Wangsness Wehe 2017 University of Wyoming

Minimum Rank Of Skew-Symmetric Matrices Described By A Graph, Mary Allison, Elizabeth Bodine, Luz Maria Dealba, Joyati Debnath, Laura Deloss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader, Amy Wangsness Wehe

Leslie Hogben

The minimum (symmetric) rank of a simple graph G over a field F is the smallest possible rank among all symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. The problem of determining minimum (symmetric) rank has been studied extensively. We define the minimum skew rank of a simple graph G to be the smallest possible rank among all skew-symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We apply ...


The Minimum Rank Of Symmetric Matrices Described By A Graph: A Survey, Shaun M. Fallat, Leslie Hogben 2017 University of Regina

The Minimum Rank Of Symmetric Matrices Described By A Graph: A Survey, Shaun M. Fallat, Leslie Hogben

Leslie Hogben

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper surveys the current state of knowledge on the problem of determining the minimum rank of a graph and related issues.


The Copositive Completion Problem: Unspecified Diagonal Entries, Leslie Hogben 2017 Iowa State University

The Copositive Completion Problem: Unspecified Diagonal Entries, Leslie Hogben

Leslie Hogben

In [L. Hogben, C.R. Johnson, R. Reams, The copositive matrix completion problem, Linear Algebra Appl. 408 (2005) 207–211] it was shown that any partial (strictly) copositive matrix all of whose diagonal entries are specified can be completed to a (strictly) copositive matrix. In this note we show that every partial strictly copositive matrix (possibly with unspecified diagonal entries) can be completed to a strictly copositive matrix, but there is an example of a partial copositive matrix with an unspecified diagonal entry that cannot be completed to a copositive matrix.


Digital Commons powered by bepress