Discrete Mathematics and Combinatorics Commons^™

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 …

The Maximum Rectilinear Crossing Number Of The Wheel Graph, Elie Feder

Publications and Research

We find and prove the maximum rectilinear crossing number of the wheel graph. First, we illustrate a picture of the wheel graph with many crossings to prove a lower bound. We then prove that this bound is sharp. The treatment is divided into two cases for n even and n odd.

Algebraic Structures Using Natural Class Of Intervals, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

Authors in this book introduce a new class of intervals called the natural class of intervals, also known as the special class of intervals or as natural intervals. These intervals are built using increasing intervals, decreasing intervals and degenerate intervals. We say an interval [a, b] is an increasing interval if a < b for any a, b in the field of reals R. An interval [a, b] is a decreasing interval if a > b and the interval [a, b] is a degenerate interval if a = b for a, b in the field of reals R. The natural class of intervals consists of the collection of increasing intervals, decreasing intervals and the degenerate intervals. Clearly R is contained in the natural …

Interval Semirings, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book the notion of interval semirings are introduced. The authors study and analyse semirings algebraically. Methods are given for the construction of non-associative semirings using loops and interval semirings or interval loops and semirings. Another type of non-associative semirings are introduced using groupoids and interval semirings or interval groupoids and semirings. Examples using integers and modulo integers are given. Also infinite semirings which are semifields are given using interval semigroups and semirings or semigroups and interval semirings or using groups and interval semirings. Interval groups are introduced to construct interval group interval semirings, and properties related with them …

Interval Semigroups, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book we introduce the notion of interval semigroups using intervals of the form [0, a], a is real. Several types of interval semigroups like fuzzy interval semigroups, interval symmetric semigroups, special symmetric interval semigroups, interval matrix semigroups and interval polynomial semigroups are defined and discussed. This book has eight chapters. The main feature of this book is that we suggest 241 problems in the eighth chapter. In this book the authors have defined 29 new concepts and illustrates them with 231 examples. Certainly this will find several applications. The authors deeply acknowledge Dr. Kandasamy for the proof reading …

The Positive Real Lemma And Construction Of All Realizations Of Generalized Positive Rational Functions, Daniel Alpay, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

We here extend the well known Positive Real Lemma (also known as the Kalman-Yakubovich-Popov Lemma) to complex matrix-valued generalized positive rational function, when non-minimal realizations are considered. All state space realizations are partitioned into subsets, each is identified with a set of matrices satisfying the same Lyapunov inclusion. Thus, each subset forms a convex invertible cone, cic in short, and is in fact is replica of all realizations of positive functions of the same dimensions. We then exploit this result to provide an easy construction procedure of all (not necessarily minimal) state space realizations of generalized positive functions. As a …

A Class Of Gaussian Processes With Fractional Spectral Measures, Daniel Alpay, Palle Jorgensen, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study a family of stationary increment Gaussian processes, indexed by time. These processes are determined by certain measures σ (generalized spectral measures), and our focus here is on the case when the measure σ is a singular measure. We characterize the processes arising from when σ is in one of the classes of affine self-similar measures. Our analysis makes use of Kondratiev-white noise spaces. With the use of a priori estimates and the Wick calculus, we extend and sharpen (see Theorem 7.1) earlier computations of Ito stochastic integration developed for the special case of stationary increment processes having absolutely …

Combinatorial Aspects Of Excedances And The Frobenius Complex, Eric Logan Clark

University of Kentucky Doctoral Dissertations

In this dissertation we study the excedance permutation statistic. We start by extending the classical excedance statistic of the symmetric group to the affine symmetric group eSn and determine the generating function of its distribution. The proof involves enumerating lattice points in a skew version of the root polytope of type A. Next we study the excedance set statistic on the symmetric group by defining a related algebra which we call the excedance algebra. A combinatorial interpretation of expansions from this algebra is provided. The second half of this dissertation deals with the topology of the Frobenius complex, that …

A Note On Solid Coloring Of Pure Simplicial Complexes, Joseph O'Rourke

Computer Science: Faculty Publications

We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in R^d may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R² this says that any planar map all of whose faces are triangles may be 3-colored, and in R³ it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.

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.

Slider-Pinning Rigidity: A Maxwell-Laman-Type Theorem, Ileana Streinu, Louis Theran

Computer Science: Faculty Publications

We define and study slider-pinning rigidity, giving a complete combinatorial characterization. This is done via direction-slider networks, which are a generalization of Whiteley’s direction networks.

Building Graphs From Colored Trees, Rachel M. Esselstein, Peter Winkler

Dartmouth Scholarship

We will explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely, fix a radius $\rho$ and let $N(G)$ be the set of isomorphism classes of $\rho$-neighborhoods of vertices of $G$ where $G$ is a graph whose vertices are colored (not necessarily properly) by colors from a fixed finite palette. The root of the neighborhood will be the unique vertex at the "center" of the graph. Given a set S of colored graphs with a unique root, when is there a graph G with N (G) = S? Or N (G) ⊂ …

Combinatorial Trigonometry With Chebyshev Polynomials, Arthur T. Benjamin, Larry Ericksen, Pallavi Jayawant, Mark Shattuck

All HMC Faculty Publications and Research

We provide a combinatorial proof of the trigonometric identity cos(n_{θ) =} T_ncos(θ),
where T_n is the Chebyshev polynomial of the first kind. We also provide combinatorial proofs of other trigonometric identities, including those involving Chebyshev polynomials of the second kind.

Combinatorially Composing Chebyshev Polynomials, Arthur T. Benjamin, Daniel Walton '07

All HMC Faculty Publications and Research

We present a combinatorial proof of two fundamental composition identities associated with Chebyshev polynomials. Namely, for all m, n ≥ 0, T_m(T_n(x)) = T_mn(x) and U_m-1 (T_n(x))U_n-1(x) = U_mn-1(x).

A Predictive Model For Secondary Rna Structure Using Graph Theory And A Neural Network., Denise Renee Koessler

Electronic Theses and Dissertations

In this work we use a graph-theoretic representation of secondary RNA structure found in the database RAG: RNA-As-Graphs. We model the bonding of two RNA secondary structures to form a larger structure with a graph operation called merge. The resulting data from each tree merge operation is summarized and represented by a vector. We use these vectors as input values for a neural network and train the network to recognize a tree as RNA-like or not based on the merge data vector.

The network correctly assigned a high probability of RNA-likeness to trees identified as RNA-like in the RAG database, …