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.

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.

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 …

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.

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 …

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 …