Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

1,116 Full-Text Articles 1,296 Authors 292,068 Downloads 114 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

1,116 full-text articles. Page 43 of 44.

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

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θ) = Tncos(θ),
where Tn 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 2010 Harvey Mudd College

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, Tm(Tn(x)) = Tmn(x) and Um-1 (Tn(x))Un-1(x) = Umn-1(x).


The Maximum Clique Problem: Algorithms, Applications, And Implementations, John David Eblen 2010 University of Tennessee, Knoxville

The Maximum Clique Problem: Algorithms, Applications, And Implementations, John David Eblen

Doctoral Dissertations

Computationally hard problems are routinely encountered during the course of solving practical problems. This is commonly dealt with by settling for less than optimal solutions, through the use of heuristics or approximation algorithms. This dissertation examines the alternate possibility of solving such problems exactly, through a detailed study of one particular problem, the maximum clique problem. It discusses algorithms, implementations, and the application of maximum clique results to real-world problems. First, the theoretical roots of the algorithmic method employed are discussed. Then a practical approach is described, which separates out important algorithmic decisions so that the algorithm can be easily …


An Overview Of The Geometry And Combinatorics Of The Macdonald Polynomial And Q-T Catalan Number, Tian Liang 2010 University of Pennsylvania

An Overview Of The Geometry And Combinatorics Of The Macdonald Polynomial And Q-T Catalan Number, Tian Liang

Publicly Accessible Penn Dissertations

We will explore the combinatorial and geometric properties related to the Macdonald polynomials and the diagonal harmonics. We have the combinatorial Macdonald polynomial formula that ts the dening conditions directly. The shue conjecture gives an elegant expression of the Frobenius series of the diagonal harmonics. While the geometric properties of the Hilbert scheme and schemes over it provides explanations from a dierent perspective. We use examples to show that these two approaches arrive at the same goal.


Total Domination Dot Critical And Dot Stable Graphs., Stephanie Anne Marie McMahon 2010 East Tennessee State University

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 …


A Predictive Model For Secondary Rna Structure Using Graph Theory And A Neural Network., Denise Renee Koessler 2010 East Tennessee State University

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


Profiles Of Large Combinatorial Structures, Michael T. Lugo 2010 University of Pennsylvania

Profiles Of Large Combinatorial Structures, Michael T. Lugo

Publicly Accessible Penn Dissertations

We derive limit laws for random combinatorial structures using singularity analysis of generating functions. We begin with a study of the Boltzmann samplers of Flajolet and collaborators, a useful method for generating large discrete structures at random which is useful both for providing intuition and conjecture and as a possible proof technique. We then apply generating functions and Boltzmann samplers to three main classes of objects: permutations with weighted cycles, involutions, and integer partitions. Random permutations in which each cycle carries a multiplicative weight $\sigma$ have probability $(1-\gamma)^\sigma$ of having a random element be in a cycle of length longer …


An Algorithm To Generate Two-Dimensional Drawings Of Conway Algebraic Knots, Jen-Fu Tung 2010 Western Kentucky University

An Algorithm To Generate Two-Dimensional Drawings Of Conway Algebraic Knots, Jen-Fu Tung

Masters Theses & Specialist Projects

The problem of finding an efficient algorithm to create a two-dimensional embedding of a knot diagram is not an easy one. Typically, knots with a large number of crossings will not nicely generate two-dimensional drawings. This thesis presents an efficient algorithm to generate a knot and to create a nice two-dimensional embedding of the knot. For the purpose of this thesis a drawing is “nice” if the number of tangles in the diagram consisting of half-twists is minimal. More specifically, the algorithm generates prime, alternating Conway algebraic knots in O(n) time where n is the number of crossings …


Discrete Fractional Calculus And Its Applications To Tumor Growth, Sevgi Sengul 2010 Western Kentucky University

Discrete Fractional Calculus And Its Applications To Tumor Growth, Sevgi Sengul

Masters Theses & Specialist Projects

Almost every theory of mathematics has its discrete counterpart that makes it conceptually easier to understand and practically easier to use in the modeling process of real world problems. For instance, one can take the "difference" of any function, from 1st order up to the n-th order with discrete calculus. However, it is also possible to extend this theory by means of discrete fractional calculus and make n- any real number such that the ½-th order difference is well defined. This thesis is comprised of five chapters that demonstrate some basic definitions and properties of discrete fractional calculus …


Computational Circle Packing: Geometry And Discrete Analytic Function Theory, Gerald Lee Orick 2010 University of Tennessee, Knoxville

Computational Circle Packing: Geometry And Discrete Analytic Function Theory, Gerald Lee Orick

Doctoral Dissertations

Geometric Circle Packings are of interest not only for their aesthetic appeal but also their relation to discrete analytic function theory. This thesis presents new computational methods which enable additional practical applications for circle packing geometry along with providing a new discrete analytic interpretation of the classical Schwarzian derivative and traditional univalence criterion of classical analytic function theory. To this end I present a new method of computing the maximal packing and solving the circle packing layout problem for a simplicial 2-complex along with additional geometric variants and applications. This thesis also presents a geometric discrete Schwarzian quantity whose value …


On The Non-Existence Of A Projective (75, 4,12, 5) Set In Pg(3, 7), Aaron C.S. Chan, James A. Davis, Jonathan Jedwab 2010 University of Richmond

On The Non-Existence Of A Projective (75, 4,12, 5) Set In Pg(3, 7), Aaron C.S. Chan, James A. Davis, Jonathan Jedwab

Math and Computer Science Faculty Publications

We show by a combination of theoretical argument and computer search that if a projective (75, 4, 12, 5) set in PG(3, 7) exists then its automorphism group must be trivial. This corresponds to the smallest open case of a coding problem posed by H. Ward in 1998, concerning the possible existence of an infinite family of projective two-weight codes meeting the Griesmer bound.


Some Implications Of Chu's 10Ψ10 Generalization Of Bailey's 6Ψ6 Summation Formula, James McLaughlin, Andrew Sills, Peter Zimmer 2010 West Chester University of Pennsylvania

Some Implications Of Chu's 10Ψ10 Generalization Of Bailey's 6Ψ6 Summation Formula, James Mclaughlin, Andrew Sills, Peter Zimmer

Mathematics Faculty Publications

Lucy Slater used Bailey's 6Ã6 summation formula to derive the Bailey pairs she used to construct her famous list of 130 identities of the Rogers-Ramanujan type.

In the present paper we apply the same techniques to Chu's 10Ã10 generalization of Bailey's formula to produce quite general Bailey pairs. Slater's Bailey pairs are then recovered as special limiting cases of these more general pairs.

In re-examining Slater's work, we find that her Bailey pairs are, for the most part, special cases of more general Bailey pairs containing one or more free parameters. Further, we also find new …


Recognizing Graph Theoretic Properties With Polynomial Ideals, Jesus A. De Loera, Christopher J. HIllar, Peter N. Malkin, Mohamed Omar 2010 University of California - Davis

Recognizing Graph Theoretic Properties With Polynomial Ideals, Jesus A. De Loera, Christopher J. Hillar, Peter N. Malkin, Mohamed Omar

All HMC Faculty Publications and Research

Many hard combinatorial problems can be modeled by a system of polynomial equations. N. Alon coined the term polynomial method to describe the use of nonlinear polynomials when solving combinatorial problems. We continue the exploration of the polynomial method and show how the algorithmic theory of polynomial ideals can be used to detect k-colorability, unique Hamiltonicity, and automorphism rigidity of graphs. Our techniques are diverse and involve Nullstellensatz certificates, linear algebra over finite fields, Gröbner bases, toric algebra, convex programming, and real algebraic geometry.


Snort: A Combinatorial Game, Keiko Kakihara 2010 California State University, San Bernardino

Snort: A Combinatorial Game, Keiko Kakihara

Theses Digitization Project

This paper focuses on the game Snort, which is a combinatorial game on graphs. This paper will explore the characteristics of opposability through examples. More fully, we obtain some neccessary conditions for a graph to be opposable. Since an opposable graph guarantees a second player win, we examine graphs that result in a first player win.


Discrete-Time Multi-Scale Systems, Daniel Alpay, Mamadou Mboup 2010 Chapman University

Discrete-Time Multi-Scale Systems, Daniel Alpay, Mamadou Mboup

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce multi-scale filtering by the way of certain double convolution systems. We prove stability theorems for these systems and make connections with function theory in the poly-disc. Finally, we compare the framework developed here with the white noise space framework, within which a similar class of double convolution systems has been defined earlier.


Interval Linear Algebra, Florentin Smarandache, W.B. Vasantha Kandasamy 2010 University of New Mexico

Interval Linear Algebra, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

This Interval arithmetic or interval mathematics developed in 1950’s and 1960’s by mathematicians as an approach to putting bounds on rounding errors and measurement error in mathematical computations. However no proper interval algebraic structures have been defined or studies. In this book we for the first time introduce several types of interval linear algebras and study them. This structure has become indispensable for these concepts will find applications in numerical optimization and validation of structural designs. In this book we use only special types of intervals and introduce the notion of different types of interval linear algebras and interval vector …


Linear Stochastic State Space Theory In The White Noise Space Setting, Daniel Alpay, David Levanony, Ariel Pinhas 2010 Chapman University

Linear Stochastic State Space Theory In The White Noise Space Setting, Daniel Alpay, David Levanony, Ariel Pinhas

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study state space equations within the white noise space setting. A commutative ring of power series in a countable number of variables plays an important role. Transfer functions are rational functions with coefficients in this commutative ring, and are characterized in a number of ways. A major feature in our approach is the observation that key characteristics of a linear, time invariant, stochastic system are determined by the corresponding characteristics associated with the deterministic part of the system, namely its average behavior.


Krein Systems And Canonical Systems On A Finite Interval: Accelerants With A Jump Discontinuity At The Origin And Continuous Potentials, Daniel Alpay, I. Gohberg, M. A. Kaashoek, L. Lerer, A. Sakhnovich 2010 Chapman University

Krein Systems And Canonical Systems On A Finite Interval: Accelerants With A Jump Discontinuity At The Origin And Continuous Potentials, Daniel Alpay, I. Gohberg, M. A. Kaashoek, L. Lerer, A. Sakhnovich

Mathematics, Physics, and Computer Science Faculty Articles and Research

This paper is devoted to connections between accelerants and potentials of Krein systems and of canonical systems of Dirac type, both on a finite interval. It is shown that a continuous potential is always generated by an accelerant, provided the latter is continuous with a possible jump discontinuity at the origin. Moreover, the generating accelerant is uniquely determined by the potential. The results are illustrated on pseudo-exponential potentials. The paper is a continuation of the earlier paper of the authors [1] dealing with the direct problem for Krein systems.


Ergodic And Combinatorial Proofs Of Van Der Waerden's Theorem, Matthew Samuel Rothlisberger 2010 Claremont McKenna College

Ergodic And Combinatorial Proofs Of Van Der Waerden's Theorem, Matthew Samuel Rothlisberger

CMC Senior Theses

Followed two different proofs of van der Waerden's theorem. Found that the two proofs yield important information about arithmetic progressions and the theorem. van der Waerden's theorem explains the occurrence of arithmetic progressions which can be used to explain such things as the Bible Code.


On The Characteristics Of A Class Of Gaussian Processes Within The White Noise Space Setting, Daniel Alpay, Haim Attia, David Levanony 2010 Chapman University

On The Characteristics Of A Class Of Gaussian Processes Within The White Noise Space Setting, Daniel Alpay, Haim Attia, David Levanony

Mathematics, Physics, and Computer Science Faculty Articles and Research

Using the white noise space framework, we define a class of stochastic processes which include as a particular case the fractional Brownian motion and its derivative. The covariance functions of these processes are of a special form, studied by Schoenberg, von Neumann and Krein.


Digital Commons powered by bepress