Physical Sciences and Mathematics Commons^™

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.

Counting 1324, 4231-Avoiding Permutations, Michael H. Albert, M. D. Atkinson, Vincent Vatter

Dartmouth Scholarship

A complete structural description and enumeration is found for permutations that avoid both 1324 and 4231.

Sparse Hypergraphs And Pebble Game Algorithms, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V^′⊂V spans more than k|V^′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu [A. Lee, I. Streinu, Pebble game algorithms …

Operations Research Methods For Optimization In Radiation Oncology, M Ehrgott, Allen Holder

Mathematical Sciences Technical Reports (MSTR)

Operations Research has a successful tradition of applying mathematical analysis to a wide range of applications, with one of the burgeoning areas of growth being in medical physics. The original application was in the optimal design of the influence map for a radiotherapy treatment, a problem that has continued to receive attention. However, operations research has been applied to other clinical problems like patient scheduling, vault design, and image alignment. The overriding theme of this article is to present how techniques in operations research apply to clinical problems, which we accomplish in three parts. First, we present the perspective from …

The Last Of The Mixed Triple Systems., Ernest Jum

Electronic Theses and Dissertations

In this thesis, we consider the decomposition of the complete mixed graph on v vertices denoted M_v, into every possible mixed graph on three vertices which has (like M_v) twice as many arcs as edges. Direct constructions are given in most cases. Decompositions of theλ-fold complete mixed graph λM_v, are also studied.

Independent Domination In Complementary Prisms., Joel Agustin Gongora

Electronic Theses and Dissertations

Let G be a graph and G̅ be the complement of G. The complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. For example, if G is a 5-cycle, then GG̅ is the Petersen graph. In this paper we investigate independent domination in complementary prisms.

Solving The P-Median Problem With Insights From Discrete Vector Quantization, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

The goals of this paper are twofold. First, we formally equate the p-median problem from facility location to the optimal design of a vector quantizer. Second, we use the equivalence to show that the Maranzana Algorithm can be interpreted as a projected Lloyd Algorithm, a fact that improves complexity. Numerical results verify significant improvements in run-time.

A Decomposition Of The Pure Parsimony Problem, Allen Holder, Thomas M. Langley

Mathematical Sciences Technical Reports (MSTR)

We partially order a collection of genotypes so that we can represent the problem of inferring the least number of haplotypes in terms of substructures we call g-lattices. This representation allows us to prove that if the genotypes partition into chains with certain structure, then the NP-Hard problem can be solved efficiently. Even without the specified structure, the decomposition shows how to separate the underlying integer programming model into smaller models.

A Clustering Approach For Optimizing Beam Angles In Imrt Planning, Gino J. Lim, Allen Holder, Josh Reese

Mathematical Sciences Technical Reports (MSTR)

In this paper we introduce a p-median problem based clustering heuristic for selecting efficient beam angles for intensity-modulated radiation therapy. The essence of the method described here is the clustering of beam angles according to probability that an angle will be observed in the final solution and similarities among different angles and the selection of a representative angle from each of the p resulting cluster cells. We conduct experiments using several combinations of modeling parameters to find the conditions where the heuristic best performs. We found a combination of such parameters that outperformed all other parameters on three of the …

Compression Theorems For Periodic Tilings And Consequences, Arthur T. Benjamin, Alex K. Eustis '06, Mark A. Shattuck

All HMC Faculty Publications and Research

We consider a weighted square-and-domino tiling model obtained by assigning real number weights to the cells and boundaries of an n-board. An important special case apparently arises when these weights form periodic sequences. When the weights of an nm-tiling form sequences having period m, it is shown that such a tiling may be regarded as a meta-tiling of length n whose weights have period 1 except for the first cell (i.e., are constant). We term such a contraction of the period in going from the longer to the shorter tiling as "period compression". It turns out that …

Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman

Mathematical Sciences Technical Reports (MSTR)

The absence of an efficient algorithm to solve the Discrete Logarithm Problem is often exploited in cryptography. While exponentiation with a modulus is extremely fast with a modern computer, the inverse is decidedly not. At the present time, the best algorithms assume that the inverse mapping is completely random. Yet there is at least some structure, and to uncover additional structure that may be useful in constructing or refining algorithms, statistical methods are employed to compare modular exponential mappings to random mappings. More concretely, structure will be defined by representing the mappings as functional graphs and using parameters from graph …

Discrete Logarithm Over Composite Moduli, Marcus L. Mace

Mathematical Sciences Technical Reports (MSTR)

In an age of digital information, security is of utmost importance. Many encryption schemes, such as the Diffie-Hellman Key Agreement and RSA Cryptosystem, use a function which maps x to y by a modular power map with generator g. The inverse of this function - trying to find x from y - is called the discrete logarithm problem. In most cases, n is a prime number. In some cases, however, n may be a composite number. In particular, we will look at when n = p^b for a prime p. We will show different techniques of obtaining graphs of this …

Structural Properties Of Power Digraphs Modulo N, Joseph Kramer-Miller

Mathematical Sciences Technical Reports (MSTR)

We define G(n, k) to be a directed graph whose set of vertices is {0, 1, ..., n−1} and whose set of edges is defined by a modular relation. We say that G(n, k) is symmetric of order m if we can partition G(n, k) into subgraphs, each containing m components, such that all the components in a subgraph are isomorphic. We develop necessary and sufficient conditions for G(n, k) to contain symmetry when n is odd and square-free. Additionally, we use group theory to describe the structural properties of the subgraph of G(n, k) containing only those vertices relatively …

Some Properties Of Yao Y4 Subgraphs, Joseph O'Rourke

Computer Science: Faculty Publications

The Yao graph for k = 4, Y₄, is naturally partitioned into four subgraphs, one per quadrant. We show that the subgraphs for one quadrant differ from the subgraphs for two adjacent quadrants in three properties: planarity, connectedness, and whether the directed graphs are spanners.

Decompositions Of Mixed Graphs With Partial Orientations Of The P4., Adam M. Meadows

Electronic Theses and Dissertations

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x …

Locating-Domination In Complementary Prisms., Kristin Renee Stone Holmes

Electronic Theses and Dissertations

Let G = (V (G), E(G)) be a graph and G̅ be the complement of G. The complementary prism of G, denoted GG̅, is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. A set D ⊆ V (G) is a locating-dominating set of G if for every u ∈ V (G)D, its neighborhood N(u)⋂D is nonempty and distinct from N( …

Cyclic, F-Cyclic, And Bicyclic Decompositions Of The Complete Graph Into The 4-Cycle With A Pendant Edge., Daniel Shelton Cantrell

Electronic Theses and Dissertations

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of:

(1) a single cycle of length v,

(2) f fixed points and a cycle of length v − f, or

(3) two disjoint cycles.

The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of K_v.

Extremal Random Walks On Trees, Meng Wang

Mathematics, Statistics, and Computer Science Honors Projects

We study random walks on trees, where we iteratively move from one vertex to a randomly chosen adjacent vertex. We study two quantities arising in random walks: the hitting time and the mixing time. The hitting time is the expected number of steps to walk between a chosen pair of vertices. The mixing time is the expected number of steps before the distribution of the current state is proportional to its degree. For a fixed tree size, we prove that the star is the unique minimizing structure and the path is the unique maximizing structure for both quantities.

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 …

The Maximum Rectilinear Crossing Number Of The N Dimensional Cube Graph, Matthew Alpert, Elie Feder, Heiko Harborth, Sheldon Klein

Publications and Research

We find a.nd prove the maximum rectilinear crossing n1.1mber of the three-dimensional cube graph (Q₃). We demonstrate a method of drawing then-cube graph, Q_n., with many crossings, and thus find a lower bound for the maximum rectilinear crossing number of Q_n. We conjecture that this bound is sharp. We also prove an upper bound for the maximum rectilinear crossing number of Q_n.

The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz

Faculty Publications & Research

Erdős and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West

Faculty Publications & Research

A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γ_R(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γ_R(G) + …

Fixing Numbers Of Graphs And Groups, Courtney Gibbons, Joshua D. Laison

Articles

The fixing number of a graph G is the smallest cardinality of a set of vertices S such that only the trivial automorphism of G fixes every vertex in S. The fixing set of a group Γ is the set of all fixing numbers of finite graphs with automorphism group Γ. Several authors have studied the distinguishing number of a graph, the smallest number of labels needed to label G so that the automorphism group of the labeled graph is trivial. The fixing number can be thought of as a variation of the distinguishing number in which every label …

On The Number Of K-Gons In Finite Projective Planes, Felix Lazebnik, Keith Mellinger, Oscar Vega

Mathematics

Let π = πq denote a finite projective plane of order q, and let G = Levi(π) be the bipartite point-line incidence graph of π. For k ≥ 3, let c2k(π) denote the number of cycles of length 2k in G. Are the numbers c2k(π) the same for all πq? We prove that this is the case for k = 3, 4, 5, 6 by computing these numbers.

Some More Identities Of Rogers-Ramanujan Type, Douglas Bowman, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

In this we paper we prove several new identities of the Rogers-Ramanujan-Slater type. These identities were found as the result of computer searches. The proofs involve a variety of techniques, including series-series identities, Bailey pairs, a theorem of Watson on basic hypergeometric series, generating functions and miscellaneous methods.

Lifting Bailey Pairs To Wp-Bailey Pairs, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

A pair of sequences (αn(a,k,q),βn(a,k,q)) such that α0(a,k,q)=1 and βn(a,k,q)=∑nj=0(k/a;q)n−j(k;q)n+j(q;q)n−j(aq;q)n+jαj(a,k,q) is termed aWP-Bailey Pair . Upon setting k=0 in such a pair we obtain a Bailey pair. In the present paper we consider the problem of “lifting” a Bailey pair to a WP-Bailey pair, and use some of the new WP-Bailey pairs found in this way to derive some new identities between basic hypergeometric series and new single-sum and double-sum identities of the Rogers–Ramanujan–Slater type.

Combinatorics Of Ramanujan-Slater Type Identities, James Mclaughlin, Andrew Sills

Mathematics Faculty Publications

We provide the missing member of a family of four q-series identities related to the modulus 36, the other members having been found by Ramanujan and Slater. We examine combinatorial implications of the identities in this family, and of some of the identities we considered inIdentities of the Ramanujan-Slater type related to the moduli 18 and 24.

Rogers-Ramanujan Computer Searches, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

We describe three computer searches (in PARI/GP, Maple, and Mathematica, respectively) which led to the discovery of a number of identities of Rogers–Ramanujan type and identities of false theta functions.

Integral Orthogonal Bases Of Small Height For Real Polynomial Spaces, Lenny Fukshansky

CMC Faculty Publications and Research

Let P_N(R) be the space of all real polynomials in N variables with the usual inner product < , > on it, given by integrating over the unit sphere. We start by deriving an explicit combinatorial formula for the bilinear form representing this inner product on the space of coefficient vectors of all polynomials in P_N(R) of degree ≤ M. We exhibit two applications of this formula. First, given a finite dimensional subspace V of P_N(R) defined over Q, we prove the existence of an orthogonal basis for (V, < , >), consisting of polynomials of small height …

The Maximum Of The Maximum Rectilinear Crossing Numbers Of D-Regular Graphs Of Order N, Matthew Alpert, Elie Feder, Heiko Harborth

Publications and Research

We extend known results regarding the maximum rectilinear crossing number of the cycle graph (Cn) and the complete graph (Kn ) to the class of general d-regular graphs Rn,d. We present the generalized star drawings of the d-regular graphs Sn,d of order n where n + d ≡ 1 (mod 2) and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of Sn,d for n ≡ d ≡ 0 (mod 2) is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by …