Discrete Mathematics and Combinatorics Commons^™

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, …

Total Domination Dot Critical And Dot Stable Graphs., Stephanie Anne Marie Mcmahon

Electronic Theses and Dissertations

Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total …