Mathematics Commons^™

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar

All HMC Faculty Publications and Research

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root …

Two-Coloring Cycles In Complete Graphs, Claire Djang

Honors Papers

Inspired by an investigation of Ramsey theory, this paper aims to clarify in further detail a number of results regarding the existence of monochromatic cycles in complete graphs whose edges are colored red or blue. The second half focuses on a proof given by Gyula Károlyi and Vera Rosta for the solution of all R(Cn,Ck).

Generating Minimal T-Wise Test Suites, Luis C. Gutierrez, Carlos Nieto, Francisco Zapata, Martine Ceberio

COURI Symposium Abstracts, Summer 2012

As the use of computing devices increases every day, users rely on the adequate functioning of software. When software is not tested properly, it can yield erroneous information or a complete failure of the system. The NIST estimates that defective software cost the United States economy close to $60 billion a year. Therefore, there is a need to develop software testing techniques that are time and cost effective. Fully testing software under all possible combinations of parameters values cannot be reduced. However, testing can focus on covering all combinations of subsets of parameters and empirical data shows that doing so …

The Rook-Brauer Algebra, Elise G. Delmas

Mathematics, Statistics, and Computer Science Honors Projects

We introduce an associative algebra RB_k(x) that has a basis of rook-Brauer diagrams. These diagrams correspond to partial matchings on 2k vertices. The rook-Brauer algebra contains the group algebra of the symmetric group, the Brauer algebra, and the rook monoid algebra as subalgebras. We show that the basis of RB_k(x) is generated by special diagrams s_i, t_i (1 <= i < k) and p_j (1 <= j <= k), where the s_i are the simple transpositions that generated the symmetric group S_k, the t_i are the "contraction maps" which generate the …

Generating Minimal Pair-Wise Covering Test Suites, Luis C. Gutierrez ^, Martine Ceberio *

COURI Symposium Abstracts, Spring 2012

Software is ubiquitous and needs to be reliable. Software testing therefore plays an important role in software development. Proper testing a software system informs about its quality and reliability so as to prevent unexpected behavior during system execution. One of the methods to prevent failures consists in testing a system under different input values, but when all possible input values are tested, an impractical number of test cases might result. In software testing, pair-wise testing is a combinatorial technique which uses combination of pair input values to generate test cases. Using pair-wise testing dramatically reduces the number of test cases, …

Linear Combinations Of Heuristics For Examination Timetabling, Jay Yellen, Edmund K. Burke, Nam Pham

Faculty Publications

Although they are simple techniques from the early days of timetabling research, graph colouring heuristics are still attracting significant research interest in the timetabling research community. These heuristics involve simple ordering strategies to first select and colour those vertices that are most likely to cause trouble if deferred until later. Most of this work used a single heuristic to measure the difficulty of a vertex. Relatively less attention has been paid to select an appropriate colour for the selected vertex. Some recent work has demonstrated the superiority of combining a number of different heuristics for vertex and colour selection. In …

Some Aspects Of Toric Topology., Soumen Sarkar Dr.

Doctoral Theses

The main goal of this thesis is to study the topology of torus actions on manifolds and orbifolds. In algebraic geometry actions of the torus (C * ) n on algebraic varieties with nice properties produce bridges between geometry and combinatorics see [Dan78], [Oda88] and [Ful93]. We see a similar bridge called moment map for Hamiltonian action of compact torus on symplectic manifolds see [Aud91] and [Gui94]. In particular whenever the manifold is compact the image of moment map is a simple polytope, the orbit space of the action. A topological counterpart called quasitoric manifolds, a class of topological manifolds …

Lefschetz Properties And Enumerations, David Cook Ii

Theses and Dissertations--Mathematics

An artinian standard graded algebra has the weak Lefschetz property if the multiplication by a general linear form induces maps of maximal rank between consecutive degree components. It has the strong Lefschetz property if the multiplication by powers of a general linear form also induce maps of maximal rank between the appropriate degree components. These properties are mainly studied for the constraints they place, when present, on the Hilbert series of the algebra. While the majority of research on the Lefschetz properties has focused on characteristic zero, we primarily consider the presence of the properties in positive characteristic. We study …

Dihedral Cayley Directed Strongly Regular Graphs, Jose Jonathan Gamez

Open Access Theses & Dissertations

A graph is a directed strongly regular graph (DSRG) if and only if the number of paths of length 2 from x to y is: λ, if there is an edge from x to y; μ, if there is not an edge from x to y (with x not equal to y); and t, if x = y. For every vertex in G, the in-degree and out-degree is k. The number of vertices in G is denoted by v. If G is a group and S a subset of G, then the …

Coloring Problems, Thomas Antonio Charles Chartier

Boise State University Theses and Dissertations

This thesis considers several coloring problems all of which have a combinatorial flavor. We review some results on the chromatic number of the plane, and improve a bound on the value of regressive Ramsey numbers. The main work of this thesis considers the problem of whether given any n ≥ 1; one can color Z+ in such a way that for all a ϵ Z+ the numbers a, 2a, 3a, ..., na are assigned different colors. Such colorings are referred to as satisfactory. We provide a sufficient condition for guaranteeing the existence of satisfactory colorings and analyze the …

Combinatorics Of Two-Toned Tilings, Arthur T. Benjamin, Phyllis Chinn, Jacob N. Scott '11, Greg Simay

All HMC Faculty Publications and Research

We introduce the function a(r, n) which counts tilings of length n + r that utilize white tiles (whose lengths can vary between 1 and n) and r identical red squares. These tilings are called two-toned tilings. We provide combinatorial proofs of several identities satisfied by a(r, n) and its generalizations, including one that produces kth order Fibonacci numbers. Applications to integer partitions are also provided.

Spectral Properties Of Large Dimensional Random Circulant Type Matrices., Koushik Saha Dr.

Doctoral Theses

Consider a sequence of matrices whose dimension increases to infinity. Suppose the entries of this sequence of matrices are random. These matrices with increasing dimension are called large dimensional random matrices (LDRM).Practices of random matrices, more precisely the properties of their eigenvalues, has emerged first from data analysis (beginning with Wishart (1928) [132]) and then from statistical models for heavy nuclei atoms (beginning with Wigner (1955) [130]). To insist on its physical applications, a mathematical theory of the spectrum of the random matrices began to emerge with the work of E. P. Wigner, F. J. Dyson, M. L. Mehta, C. …

A New Framework For Network Disruption, Susan E. Martonosi, Doug Altner, Michael Ernst, Elizabeth Ferme, Kira Langsjoen, Danika Lindsay, Sean S. Plott '08, Andrew S. Ronan

All HMC Faculty Publications and Research

Traditional network disruption approaches focus on disconnecting or lengthening paths in the network. We present a new framework for network disruption that attempts to reroute flow through critical vertices via vertex deletion, under the assumption that this will render those vertices vulnerable to future attacks. We define the load on a critical vertex to be the number of paths in the network that must flow through the vertex. We present graph-theoretic and computational techniques to maximize this load, firstly by removing either a single vertex from the network, secondly by removing a subset of vertices.

The Combinatorialization Of Linear Recurrences, Arthur T. Benjamin, Halcyon Derks, Jennifer J. Quinn

All HMC Faculty Publications and Research

We provide two combinatorial proofs that linear recurrences with constant coefficients have a closed form based on the roots of its characteristic equation. The proofs employ sign-reversing involutions on weighted tilings.

Third And Fourth Binomial Coefficients, Arthur T. Benjamin, Jacob N. Scott '11

All HMC Faculty Publications and Research

While formulas for the sums of kth binomial coefficients can be shown inductively or algebraically, these proofs give little insight into the combinatorics involved. We prove formulas for the sums of 3rd and 4th binomial coefficients via purely combinatorial arguments.

Zero-Sum Magic Graphs And Their Null Sets, Samuel M. Hansen

UNLV Theses, Dissertations, Professional Papers, and Capstones

For any element h of the Natural numbers, a graph G=(V,E), with vertex set V and edge set E, is said to be h-magic if there exists a labeling of the edge set E, using the integer group mod h such that the induced vertex labeling, the sum of all edges incident to a vertex, is a constant map. When this constant is 0 we call G a zero-sum h-magic graph. The null set of G is the set of all natural numbers h for which G admits a zero-sum h-magic labeling. A graph G is said to be uniformly …

A Census Of Vertices By Generations In Regular Tessellations Of The Plane, Alice Paul '12, Nicholas Pippenger

All HMC Faculty Publications and Research

We consider regular tessellations of the plane as infinite graphs in which q edges and q faces meet at each vertex, and in which p edges and p vertices surround each face. For 1/p + 1/q = 1/2, these are tilings of the Euclidean plane; for 1/p + 1/q < 1/2, they are tilings of the hyperbolic plane. We choose a vertex as the origin, and classify vertices into generations according to their distance (as measured by the number of edges in a shortest path) from the origin. For all p ≥ 3 and q ≥ 3 with 1/p + 1/q ≤ 1/2, we give simple combinatorial derivations of the rational generating functions for the number of vertices in each generation.

Topological And Combinatorial Properties Of Neighborhood And Chessboard Complexes, Matthew Zeckner

University of Kentucky Doctoral Dissertations

This dissertation examines the topological properties of simplicial complexes that arise from two distinct combinatorial objects. In 2003, A. Björner and M. de Longueville proved that the neighborhood complex of the stable Kneser graph SG_n,k is homotopy equivalent to a k-sphere. Further, for n = 2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the neighborhood complex of SG_n,k contains as a deformation retract the boundary complex of a simplicial polytope. Part one of this dissertation …

Sums Of Evenly Spaced Binomial Coefficients, Arthur T. Benjamin, Bob Chen '10, Kimberly Kindred

All HMC Faculty Publications and Research

We provide a combinatorial proof of a formula for the sum of evenly spaced binomial coefficients. This identity, along with a generalization, are proved by counting weighted walks on a graph.

Poset Pinball, Gkm-Compatible Subspaces, And Hessenberg Varieties, Megumi Harada, Julianna Tymoczko

Mathematics Sciences: Faculty Publications

This paper has three main goals. First, we set up a general framework to address the problem of constructing module bases for the equivariant cohomology of certain subspaces of GKM spaces. To this end we introduce the notion of a GKM-compatible subspace of an ambient GKM space. We also discuss poset-upper-triangularity, a key combinatorial notion in both GKM theory and more generally in localization theory in equivariant cohomology. With a view toward other applications, we present parts of our setup in a general algebraic and combinatorial framework. Second, motivated by our central problem of building module bases, we introduce a …

On The Characteristic Polynomial Of Regular Linear Matrix Pencil, Yan Wu, Phillip Lorren

Mathematical Sciences: Faculty Publications

Linear matrix pencil, denoted by (A,B), plays an important role in control systems and numerical linear algebra. The problem of finding the eigenvalues of (A,B) is often solved numerically by using the well-known QZ method. Another approach for exploring the eigenvalues of (A,B) is by way of its characteristic polynomial, P(λ)=A − λB. There are other applications of working directly with the characteristic polynomial, for instance, using Routh-Hurwitz analysis to count the stable roots of P(λ) and transfer function representation of control systems governed by differential-algebraic equations. In this paper, we …

Combinatorics And Topology Of Curves And Knots, Bailey Ann Ross

Boise State University Theses and Dissertations

The genus of a graph is the minimal genus of a surface into which the graph can be embedded. Four regular graphs play an important role in low dimensional topology since they arise from curves and virtual knot diagrams. Curves and virtual knots can be encoded combinatorially by certain signed words, called Gauss codes and Gauss paragraphs. The purpose of this thesis is to investigate the genus problem for these combinatorial objects: Given a Gauss word or Gauss paragraph, what is the genus of the curve or virtual knot it represents?

Sequences Of Positive Integers Containing No K-Term Arithmetic Progressions And Smooth Numbers In Short Intervals., Goutam Pal Dr.

Doctoral Theses

In my thesis I have worked on two problems:1. On sequences of positive integers containing no k terms in arithmetic progressions.2. On smooth numbers in short intervals.The first two chapters of my thesis deal with the first problem and in the rest of the thesis I have focused on the 2nd problem.In the first chapter of my thesis I have considered the function rk(N) for a fixed k ≥ 3, where, by definition, rk(N) is the cardinality of a maximal subset of N consecutive natural numbers with the property that nork terms of it are in an Arithmetic Progression (A. …

Voting, The Symmetric Group, And Representation Theory, Zajj Daugherty '05, Alexander K. Eustis '06, Gregory Minton '08, Michael E. Orrison

All HMC Faculty Publications and Research

We show how voting may be viewed naturally from an algebraic perspective by viewing voting profiles as elements of certain well-studied QS_n-modules. By using only a handful of simple combinatorial objects (e.g., tabloids) and some basic ideas from representation theory (e.g., Schur's Lemma), this allows us to recast and extend some well-known results in the field of voting theory.

Almost Avoiding Permutations, Robert Brignall, Shalosh B. Ekhad, Rebecca Smith, Vincent Vatter

Dartmouth Scholarship

The permutation π of length n, written in one-line notation as π (1)π (2)· · · π (n), is said to contain the permutation σ if π has a subsequence that is order isomorphic to σ, and each such subsequence is said to be an occurrence of σ in π or simply a σ pattern. For example, π = 491867532 contains σ = 51342 because of the subsequence π (2)π (3)π (5)π (6)π (9) = 91672. Permutation containment is easily seen to be a partial order on the set of all (finite) permutations, which we simply denote by ≤. If …

Counting On Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07

All HMC Faculty Publications and Research

Chebyshev polynomials have several elegant combinatorial interpretations. Specificially, the Chebyshev polynomials of the first kind are defined by T₀(x) = 1, T₁(x) = x, and T_n(x) = 2x T_n-1(x) - T_n-2(x). Chebyshev polynomials of the second kind U_n(x) are defined the same way, except U₁(x) = 2x. T_n and U_n are shown to count tilings of length n strips with squares and dominoes, where the tiles are given weights and sometimes color. Using these interpretations, many identities satisfied by Chebyshev polynomials can be given …

Hopf Quivers And Nichols Algebras In Positive Characteristic, Claude Cibils, Aaron Lauve, Sarah Witherspoon

Mathematics and Statistics: Faculty Publications and Other Works

We apply a combinatorial formula of the first author and Rosso, for products in Hopf quiver algebras, to determine the structure of Nichols algebras. We illustrate this technique by explicitly constructing new examples of Nichols algebras in positive characteristic. We further describe the corresponding Radford biproducts and some liftings of these biproducts, which are new finite dimensional pointed Hopf algebras.

An Alternate Approach To Alternating Sums: A Method To Die For, Arthur T. Benjamin, Jennifer J. Quinn

All HMC Faculty Publications and Research

No abstract provided in this article.

The 99th Fibonacci Identity, Arthur T. Benjamin, Alex K. Eustis '06, Sean S. Plott '08

All HMC Faculty Publications and Research

We provide elementary combinatorial proofs of several Fibonacci and Lucas number identities left open in the book Proofs That Really Count [1], and generalize these to Gibonacci sequences G_n that satisfy the Fibonacci recurrence, but with arbitrary real initial conditions. We offer several new identities as well.

[1] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions, 27, Mathematical Association of America, Washington, DC, 2003

A Combinatorial Approach To Fibonomial Coefficients, Arthur T. Benjamin, Sean S. Plott '08

All HMC Faculty Publications and Research

A combinatorial argument is used to explain the integrality of Fibonomial coefficients and their generalizations. The numerator of the Fibonomial coeffcient counts tilings of staggered lengths, which can be decomposed into a sum of integers, such that each integer is a multiple of the denominator of the Fibonomial coeffcient. By colorizing this argument, we can extend this result from Fibonacci numbers to arbitrary Lucas sequences.