Discrete Mathematics and Combinatorics Commons^™

Pattern Avoiding Partitions, Sequence A054391 And The Kernel Method, Toufik Mansour, Mark Shattuck

Applications and Applied Mathematics: An International Journal (AAM)

Sequence A054391 in OEIS, which we will denote by a_n , counts a certain two-pattern avoidance class of the permutations of size n . In this paper, we provide additional combinatorial interpretations for these numbers in terms of finite set partitions. In particular, we identify six classes of the partitions of size n , all of which have cardinality a_n and each avoiding two classical patterns. We use both algebraic and combinatorial methods to establish our results. In one apparently more difficult case, to show the result, we make use of the kernel method in solving a system …

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.

Cagan Type Rational Expectations Model On Time Scales With Their Applications To Economics, Funda Ekiz

Masters Theses & Specialist Projects

Rational expectations provide people or economic agents making future decision with available information and past experiences. The first approach to the idea of rational expectations was given approximately fifty years ago by John F. Muth. Many models in economics have been studied using the rational expectations idea. The most familiar one among them is the rational expectations version of the Cagans hyperination model where the expectation for tomorrow is formed using all the information available today. This model was reinterpreted by Thomas J. Sargent and Neil Wallace in 1973. After that time, many solution techniques were suggested to solve the …

Alternative Proofs On The Indices Of Cacti And Unicyclic Graphs With N Vertices, Sudipta Mallik

Mathematics Faculty Research

Let H_n be the cactus obtained from the star K_1,n—1 by adding _└ n—1/2_┘ independent edges between pairs of pendant vertices. Let K₁,⁺_n—1 be the unicyclic graph obtained from the star by appending one edge. In this paper we give alternative proofs of the following results: Among all cacti with n vertices, H_n is the unique cactus whose spectral radius is maximal, and among all unicyclic graphs with n vertices, K₁,⁺_n—1 is the unique unicyclic graph whose spectral radius is maximal. We also prove …

Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee

School of Computing: Technical Reports

Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.

Omnisculptures., Cihan Eroglu

Electronic Theses and Dissertations

In this thesis we will study conditions for the existence of minimal sized omnipatterns in higher dimensions. We will introduce recent work conducted on one dimensional and two dimensional patterns known as omnisequences and omnimosaics, respectively. These have been studied by Abraham et al [3] and Banks et al [2]. The three dimensional patterns we study are called omnisculptures, and will be the focus of this thesis. A (K,a) omnisequence of length n is a string of letters that contains each of the a^k words of length k over [A]={1,2,...a} as a substring. …

Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts

Mathematical Sciences Technical Reports (MSTR)

We investigate the structure and cryptographic applications of the Discrete Lambert Map (DLM). The mapping is closely related to the Discrete Log Problem, but has received far less attention since it is considered to be a more complicated map that is likely even harder to invert. However, this mapping is quite important because it underlies the security of the ElGamal Digital Signature Scheme. Using functional graphs induced by this mapping, we were able to find non-random properties that could potentially be used to exploit the ElGamal DSS.

The Square Discrete Exponentiation Map, A Wood

Mathematical Sciences Technical Reports (MSTR)

We will examine the square discrete exponentiation map and its properties. The square discrete exponentiation map is a variation on a commonly seen problem in cryptographic algorithms. This paper focuses on understanding the underlying structure of the functional graphs generated by this map. Specifically, this paper focuses on explaining the in-degree of graphs of safe primes, which are primes of the form p = 2q + 1, where q is also prime.

Polynomial Generalizations Of Two-Variable Ramanujan Type Identities, James Mclaughlin, Andrew V. Sills

Mathematics Faculty Publications

No abstract provided.

Common Edge-Unzippings For Tetrahedra, Joseph O'Rourke

Computer Science: Faculty Publications

It is shown that there are examples of distinct polyhedra, each with a Hamiltonian path of edges, which when cut, unfolds the surfaces to a common net. In particular, it is established for infinite classes of triples of tetrahedra.

The Graph Distance Game, Wayne Goddard, Anne Sinko, Peter J. Slater, Honghai Xu

Mathematics Faculty Publications

In the graph distance game, two players alternate in constructing a maximal path. The objective function is the distance between the two endpoints of the path, which one player tries to maximize and the other tries to minimize. In this note, we examine the distance game for various graphs, and provide general bounds, exact results for special graphs, and an algorithm for trees. Computer calculations suggest interesting conjectures for grids.

Mathematical Modeling, A Small Step In A Right Direction, Reza D. Noubary

Applications and Applied Mathematics: An International Journal (AAM)

Models developed by mathematicians/statisticians based on criterion such as goodness of fit often leads to a “best” model only for the data utilized. Moreover the parameters in such models often do not have physical interpretations and as such their validity cannot be checked by other means. This article makes argument against modeling processes that do not incorporate information from discipline related to the origin of data and presents an example to demonstrate benefits of doing so.

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.

The Quantum Dialectic, Logan Kelley

Pitzer Senior Theses

A philosophic account of quantum physics. The thesis is divided into two parts. Part I is dedicated to laying the groundwork of quantum physics, and explaining some of the primary difficulties. Subjects of interest will include the principle of locality, the quantum uncertainty principle, and Einstein's criterion for reality. Quantum dilemmas discussed include the double-slit experiment, observations of spin and polarization, EPR, and Bell's theorem. The first part will argue that mathematical-physical descriptions of the world fall short of explaining the experimental observations of quantum phenomenon. The problem, as will be argued, is framework of the physical descriptive schema. Part …

Universal Hypergraphs., Michael Deren

Electronic Theses and Dissertations

In this thesis, we study universal hypergraphs. What are these? Let us start with defining a universal graph as a graph on n vertices that contains each of the many possible graphs of a smaller size k < n as an induced subgraph. A hypergraph is a discrete structure on n vertices in which edges can be of any size, unlike graphs, where the edge size is always two. If all edges are of size three, then the hypergraph is said to be 3-uniform. If a 3-uniform hypergraph can have edges colored one of a colors, then it is called a …

A Predictive Model Which Uses Descriptors Of Rna Secondary Structures Derived From Graph Theory., Alissa Ann Rockney

Electronic Theses and Dissertations

The secondary structures of ribonucleic acid (RNA) have been successfully modeled with graph-theoretic structures. Often, simple graphs are used to represent secondary RNA structures; however, in this research, a multigraph representation of RNA is used, in which vertices represent stems and edges represent the internal motifs. Any type of RNA secondary structure may be represented by a graph in this manner. We define novel graphical invariants to quantify the multigraphs and obtain characteristic descriptors of the secondary structures. These descriptors are used to train an artificial neural network (ANN) to recognize the characteristics of secondary RNA structure. Using the ANN, …

Algebraic Solutions To Overdefined Systems With Applications To Cryptanalysis, Eric Crockett

Mathematical Sciences Technical Reports (MSTR)

Cryptographic algorithms are based on a wide variety of difficult problems in mathematics. One of these problems is finding a solution to a system of multivariate quadratic equations (MQ). A generalization of this problem is to find a solution to a system of higher order non-linear equations. Both of these problems are NP-hard over any field. Many cryptosystems such as AES, Serpent, Toyocrypt, and others can be reduced to some form of the MQ problem. In this paper we analyze the relinearization and XL algorithms for solving overdetermined systems of non-linear equations, as well as two variations of the XL …

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 …

Continuous Blooming Of Convex Polyhedra, Erik D. Demaine, Martin L. Demaine, Vi Hart, Joan Iacono, Stefan Langerman, Joseph O'Rourke

Computer Science: Faculty Publications

We construct the first two continuous bloomings of all convex polyhedra. First, the source unfolding can be continuously bloomed. Second, any unfolding of a convex polyhedron can be refined (further cut, by a linear number of cuts) to have a continuous blooming.

Packings And Realizations Of Degree Sequences With Specified Substructures, Tyler Seacrest

Department of Mathematics: Dissertations, Theses, and Student Research

This dissertation focuses on the intersection of two classical and fundamental areas in graph theory:  graph packing and degree sequences.  The question of packing degree sequences lies naturally in this intersection, asking when degree sequences have edge-disjoint realizations on the same vertex set.  The most significant result in this area is Kundu's k-Factor Theorem, which characterizes when a degree sequence packs with a constant sequence.  We prove a series of results in this spirit, and we particularly search for realizations of degree sequences with edge-disjoint 1-factors.  

Perhaps the most fundamental result in degree sequence theory is the Erdos-Gallai Theorem, characterizing …

Extremal Trees And Reconstruction, Andrew Ray

Department of Mathematics: Dissertations, Theses, and Student Research

Problems in two areas of graph theory will be considered.

First, I will consider extremal problems for trees. In these questions we examine the trees that maximize or minimize various invariants. For instance the number of independent sets, the number of matchings, the number of subtrees, the sum of pairwise distances, the spectral radius, and the number of homomorphisms to a fixed graph. I have two general approaches to these problems. To find the extremal trees in the collection of trees on n vertices with a fixed degree bound I use the certificate method. The certificate is a branch invariant, …

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.

A New Summation Formula For Wp-Bailey Pairs, James Mclaughlin

Mathematics Faculty Publications

No abstract provided.

Hybrid Proofs Of The Q-Binomial Theorem And Other Identities, Dennis Eichhorn, James Mclaughlin, Andrew V. Sills

Mathematics Faculty Publications

No abstract provided.

Conical Existence Of Closed Curves On Convex Polyhedra, Joseph O'Rourke, Costin Vîlcu

Computer Science: Faculty Publications

Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that "live on a cone," in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is "visible to" a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support …

Convex Polyhedra Realizing Given Face Areas, Joseph O'Rourke

Computer Science: Faculty Publications

Given n ≥ 4 positive real numbers, we prove in this note that they are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.

Coalitions And Cliques In The School Choice Problem, Sinan Aksoy, Alexander Adam Azzam, Chaya Coppersmith, Julie Glass, Gizem Karaali, Xueying Zhao, Xinjing Zhu

Pomona Faculty Publications and Research

The school choice mechanism design problem focuses on assignment mechanisms matching students to public schools in a given school district. The well-known Gale Shapley Student Optimal Stable Matching Mechanism (SOSM) is the most efficient stable mechanism proposed so far as a solution to this problem. However its inefficiency is well-documented, and recently the Efficiency Adjusted Deferred Acceptance Mechanism (EADAM) was proposed as a remedy for this weakness. In this note we describe two related adjustments to SOSM with the intention to address the same inefficiency issue. In one we create possibly artificial coalitions among students where some students modify their …

Higher Dimensional Lattice Chains And Delannoy Numbers, John S. Caughman, Charles L. Dunn, Nancy Ann Neudauer, Colin L. Starr

Faculty Publications

Fix nonnegative integers n₁ , . . ., n_d, and let L denote the lattice of points (a₁ , . . ., a_d) ∈ ℤ^d that satisfy 0 ≤ a_i ≤ n_i for 1 ≤ i ≤ d. Let L be partially ordered by the usual dominance ordering. In this paper we use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in L. Setting n_i = n (for all i) in these expressions yields a new …

Clique-Relaxed Graph Coloring, Charles Dunn, Jennifer Firkins Nordstrom, Cassandra Naymie, Erin Pitney, William Sehorn, Charlie Suer

Faculty Publications

We define a generalization of the chromatic number of a graph G called the k-clique-relaxed chromatic number, denoted χ^(k)(G). We prove bounds on χ^(k)(G) for all graphs G, including corollaries for outerplanar and planar graphs. We also define the k-clique-relaxed game chromatic number, χ_g^(k)(G), of a graph G. We prove χ_g⁽²⁾(G)≤ 4 for all outerplanar graphs G, and give an example of an outerplanar graph H with χ_g⁽²⁾(H) ≥ 3. Finally, we prove that if H is a member …