Discrete Mathematics and Combinatorics Commons^™

An Exposition Of Kasteleyn's Solution Of The Dimer Model, Eric Stucky

HMC Senior Theses

In 1961, P. W. Kasteleyn provided a baffling-looking solution to an apparently simple tiling problem: how many ways are there to tile a rectangular region with dominos? We examine his proof, simplifying and clarifying it into this nearly self-contained work.

A Combinatorial Exploration Of Elliptic Curves, Matthew Lam

HMC Senior Theses

At the intersection of algebraic geometry, number theory, and combinatorics, an interesting problem is counting points on an algebraic curve over a finite field. When specialized to the case of elliptic curves, this question leads to a surprising connection with a particular family of graphs. In this document, we present some of the underlying theory and then summarize recent results concerning the aforementioned relationship between elliptic curves and graphs. A few results are additionally further elucidated by theory that was omitted in their original presentation.

The Relaxed Edge-Coloring Game And K-Degenerate Graphs, Charles Dunn, David Morawski, Jennifer Firkins Nordstrom

Faculty Publications

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with ∆(F) = ∆, then the first player, Alice, has a winning strategy for this game with r = ∆ − j and d ≥ 2j + 2 for 0 ≤ j ≤ ∆ − 1. This both improves and generalizes the result for trees in [10]. More broadly, we generalize the main result in [10] …

Combinatorial Potpourri: Permutations, Products, Posets, And Pfaffians, Norman B. Fox

Theses and Dissertations--Mathematics

In this dissertation we first examine the descent set polynomial, which is defined in terms of the descent set statistics of the symmetric group. Algebraic and topological tools are used to explain why large classes of cyclotomic polynomials are factors of the descent set polynomial. Next the diamond product of two Eulerian posets is studied, particularly by examining the effect this product has on their cd-indices. A combinatorial interpretation involving weighted lattice paths is introduced to describe the outcome of applying the diamond product operator to two cd-monomials. Then the cd-index is defined for infinite posets, with …

The Game Chromatic Number Of Trees And Forests, Charles Dunn, Victor Larsen, Troy Retter, Kira Lindke, Dustin Toci

Faculty Publications

While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree …

Chromatic Polynomials And Orbital Chromatic Polynomials And Their Roots, Jazmin Ortiz

HMC Senior Theses

The chromatic polynomial of a graph, is a polynomial that when evaluated at a positive integer k, is the number of proper k colorings of the graph. We can then find the orbital chromatic polynomial of a graph and a group of automorphisms of the graph, which is a polynomial whose value at a positive integer k is the number of orbits of k-colorings of a graph when acted upon by the group. By considering the roots of the orbital chromatic and chromatic polynomials, the similarities and differences of these polynomials is studied. Specifically we work toward proving a conjecture …

Deletion-Induced Triangulations, Clifford T. Taylor

Theses and Dissertations--Mathematics

Let d > 0 be a fixed integer and let A ⊆ ℝ^d be a collection of n ≥ d + 2 points which we lift into ℝ^d+1. Further let k be an integer satisfying 0 ≤ k ≤ n-(d+2) and assign to each k-subset of the points of A a (regular) triangulation obtained by deleting the specified k-subset and projecting down the lower hull of the convex hull of the resulting lifting. Next, for each triangulation we form the characteristic vector defined by Gelfand, Kapranov, and Zelevinsky by assigning to each …

Polyhedral Problems In Combinatorial Convex Geometry, Liam Solus

Theses and Dissertations--Mathematics

In this dissertation, we exhibit two instances of polyhedra in combinatorial convex geometry. The first instance arises in the context of Ehrhart theory, and the polyhedra are the central objects of study. The second instance arises in algebraic statistics, and the polyhedra act as a conduit through which we study a nonpolyhedral problem.

In the first case, we examine combinatorial and algebraic properties of the Ehrhart h*-polynomial of the r-stable (n,k)-hypersimplices. These are a family of polytopes which form a nested chain of subpolytopes within the (n,k)-hypersimplex. We show that a well-studied unimodular triangulation of the (n,k)-hypersimplex restricts to a …

An Isomorphism Problem In Z2, Matt Noble

Theory & Applications of Graphs

We consider Euclidean distance graphs with vertex set ℚ² or ℤ² and address the possibility or impossibility of finding isomorphisms between such graphs. It is observed that for any distances d₁, d₂ the non-trivial distance graphs G(ℚ², d₁) and G(ℚ², d₂) are isomorphic. Ultimately it is shown that for distinct primes _p1, _p2 the non-trivial distance graphs G(ℤ², √p1) and G(ℤ², √p2) are not isomorphic. We conclude with a few additional questions related to this work.

A New Resolvent Equation For The S-Functional Calculus, Daniel Alpay, Fabrizio Colombo, Jonathan Gantner, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

The S-functional calculus is a functional calculus for (n + 1)-tuples of non necessarily commuting operators that can be considered a higher dimensional version of the classical Riesz-Dunford functional calculus for a single operator. In this last calculus, the resolvent equation plays an important role in the proof of several results. Associated with the S-functional calculus there are two resolvent operators: the left S−1 L (s, T ) and the right one S−1 R (s, T ), where s = (s0, s1, . . . , sn) ∈ Rn+1 and T = (T0, T1, . . . , Tn) is …

Operator Calculus Algorithms For Multi-Constrained Paths, Jamila Ben Slimane, Rene' Schott, Ye Qiong Song, G. Stacey Staples, Evangelia Tsiontsiou

SIUE Faculty Research, Scholarship, and Creative Activity

Classical approaches to multi-constrained routing problems generally require construction of trees and the use of heuristics to prevent combinatorial explosion. Introduced here is the notion of constrained path algebras and their application to multi-constrained path problems. The inherent combinatorial properties of these algebras make them useful for routing problems by implicitly pruning the underlying tree structures. Operator calculus (OC) methods are generalized to multiple non-additive constraints in order to develop algorithms for the multi constrained path problem and multi constrained optimization problem. Theoretical underpinnings are developed first, then algorithms are presented. These algorithms demonstrate the tremendous simplicity, flexibility and speed …

Kravchuk Polynomials And Induced/Reduced Operators On Clifford Algebras, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

Kravchuk polynomials arise as orthogonal polynomials with respect to the binomial distribution and have numerous applications in harmonic analysis, statistics, coding theory, and quantum probability. The relationship between Kravchuk polynomials and Clifford algebras is multifaceted. In this paper, Kravchuk polynomials are discovered as traces of conjugation operators in Clifford algebras, and appear in Clifford Berezin integrals of Clifford polynomials. Regarding Kravchuk matrices as linear operators on a vector space V, the action induced on the Clifford algebra over V is equivalent to blade conjugation, i.e., reflections across sets of orthogonal hyperplanes. Such operators also have a natural interpretation in …

Clifford Algebra Decompositions Of Conformal Orthogonal Group Elements, G. Stacey Staples, David Wylie

SIUE Faculty Research, Scholarship, and Creative Activity

Beginning with a finite-dimensional vector space V equipped with a nondegenerate quadratic form Q, we consider the decompositions of elements of the conformal orthogonal group CO_Q(V), defined as the direct product of the orthogonal group O_Q(V) with dilations. Utilizing the correspondence between conformal orthogonal group elements and ``decomposable'' elements of the associated Clifford algebra, Cl_Q(V), a decomposition algorithm is developed. Preliminary results on complexity reductions that can be realized passing from additive to multiplicative representations of invertible elements are also presented with examples. The approach here is …

On Representations Of Semigroups Having Hypercube-Like Cayley Graphs, Cody Cassiday, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

The $n-dimensional hypercube, or n-cube, is the Cayley graph of the Abelian group Z₂ⁿ. A number of combinatorially-interesting groups and semigroups arise from modified hypercubes. The inherent combinatorial properties of these groups and semigroups make them useful in a number of contexts, including coding theory, graph theory, stochastic processes, and even quantum mechanics. In this paper, particular groups and semigroups whose Cayley graphs are generalizations of hypercubes are described, and their irreducible representations are characterized. Constructions of faithful representations are also presented for each semigroup. The associated semigroup algebras are realized within the context …

Special Type Of Topological Spaces Using [0, N), Florentin Smarandache, W.B Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time introduce the notion of special type of topological spaces using the interval [0, n). They are very different from the usual topological spaces. Algebraic structure using the interval [0, n) have been systemically dealt by the authors. Now using those algebraic structures in this book authors introduce the notion of special type of topological spaces. Using the super subset interval semigroup special type of super interval topological spaces are built. Several interesting results in this direction are obtained. Next six types of topological spaces using subset interval pseudo ring semiring of type …

Mod Functions: A New Approach To Function Theory, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book the notion of MOD functions are defined on MOD planes. This new concept of MOD functions behaves in a very different way. Even very simple functions like y = nx has several zeros in MOD planes where as they are nice single line graphs with only (0, 0) as the only zero. Further polynomials in MOD planes do not in general follows the usual or classical laws of differentiation or integration. Even finding roots of MOD polynomials happens to be very difficult as they do not follow the fundamental theorem of algebra, viz a nth degree polynomial …

Mod Planes: A New Dimension To Modulo Theory, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book for the first time authors study mod planes using modulo intervals [0, m); 2 ≤ m ≤ ∞. These planes unlike the real plane have only one quadrant so the study is carried out in a compact space but infinite in dimension. We have given seven mod planes viz real mod planes (mod real plane) finite complex mod plane, neutrosophic mod plane, fuzzy mod plane, (or mod fuzzy plane), mod dual number plane, mod special dual like number plane and mod special quasi dual number plane. These mod planes unlike real plane or complex plane or neutrosophic …

Mod Pseudo Linear Algebras, Florentin Smarandache, W.B. Vasantha Kandasamy, K. Ilanthenral

Branch Mathematics and Statistics Faculty and Staff Publications

In this book authors for the first time elaborately study the notion of MOD vector spaces and MOD pseudo linear algebras. This study is new, innovative and leaves several open conjectures. In the first place as distributive law is not true we can define only MOD pseudo linear algebras. Secondly most of the classical theorems true in case of linear algebras are not true in case of MOD pseudo linear algebras. Finding even eigen values and eigen vectors happens to be a challenging problem. Further the notion of multidimensional MOD pseudo linear algebras are defined using the notion of MOD …

Fuzzy Abel Grassmann Groupoids, Florentin Smarandache, Madad Khan, Tariq Aziz

Branch Mathematics and Statistics Faculty and Staff Publications

Usually the models of real world problems in almost all disciplines like engineering, medical sciences, mathematics, physics, computer science, management sciences, operations research and articial intelligence are mostly full of complexities and consist of several types of uncertainties while dealing them in several occasion. To overcome these di¢ culties of uncertainties, many theories have been developed such as rough sets theory, probability theory, fuzzy sets theory, theory of vague sets, theory of soft ideals and the theory of intuitionistic fuzzy sets, theory of neutrosophic sets, Dezert-Smarandache Theory (DSmT), etc. Zadeh introduced the degree of membership/truth (t) in 1965 and dened …

Theory Of Abel Grassmann's Groupoids, Florentin Smarandache, Madad Khan

Branch Mathematics and Statistics Faculty and Staff Publications

It is common knowledge that common models with their limited boundaries of truth and falsehood are not su¢ cient to detect the reality so there is a need to discover other systems which are able to address the daily life problems. In every branch of science problems arise which abound with uncertainties and impaction. Some of these problems are related to human life, some others are subjective while others are objective and classical methods are not su¢ cient to solve such problems because they can not handle various ambiguities involved. To overcome this problem, Zadeh [67] introduced the concept of …

An Extension Of Herglotz's Theorem To The Quaternions, Daniel Alpay, Fabrizio Colombo, David P. Kimsey, Irene Sabadini, David P. Kimsey

Mathematics, Physics, and Computer Science Faculty Articles and Research

A classical theorem of Herglotz states that a function n↦r(n) from Z into Cs×s is positive definite if and only there exists a Cs×s-valued positive measure dμ on [0,2π] such that r(n)=∫2π0eintdμ(t)for n∈Z. We prove a quaternionic analogue of this result when the function is allowed to have a number of negative squares. A key tool in the argument is the theory of slice hyperholomorphic functions, and the representation of such functions which have a positive real part in the unit ball of the quaternions. We study in great detail the case of positive definite functions.

Boundary Interpolation For Slice Hyperholomorphic Schur Functions, Khaled Abu-Ghanem, Daniel Alpay, Fabrizio Colombo, David P. Kimsey, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

A boundary Nevanlinna-Pick interpolation problem is posed and solved in the quaternionic setting. Given nonnegative real numbers κ1,…,κN, quaternions p1,…,pN all of modulus 1, so that the 2-spheres determined by each point do not intersect and pu≠1 for u=1,…,N, and quaternions s1,…,sN, we wish to find a slice hyperholomorphic Schur function s so that
limr→1r∈(0,1)s(rpu)=suforu=1,…,N,
and
limr→1r∈(0,1)1−s(rpu)su¯¯¯¯¯1−r≤κu,foru=1,…,N.
Our arguments relies on the theory of slice hyperholomorphic functions and reproducing kernel Hilbert spaces.

On Algebras Which Are Inductive Limits Of Banach Spaces, Daniel Alpay, Guy Salomon

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce algebras which are inductive limits of Banach spaces and carry inequalities which are counterparts of the inequality for the norm in a Banach algebra. We then define an associated Wiener algebra, and prove the corresponding version of the well-known Wiener theorem. Finally, we consider factorization theory in these algebra, and in particular, in the associated Wiener algebra.

Unimodality Questions In Ehrhart Theory, Robert Davis

Theses and Dissertations--Mathematics

An interesting open problem in Ehrhart theory is to classify those lattice polytopes having a unimodal h^*-vector.Although various sufficient conditions have been found, necessary conditions remain a challenge. Highly-structured polytopes, such as the polytope of real doubly-stochastic matrices, have been proven to possess unimodal h^*-vectors, but the same is unknown even for small variations of it.

In this dissertation, we mainly consider two particular classes of polytopes: reflexive simplices and the polytope of symmetric real doubly-stochastic matrices. For the first class, we discuss an operation that preserves reflexivity, integral closure, and unimodality of the h^{* …}

Properly Colored Notions Of Connectivity - A Dynamic Survey, Xueliang Li, Colton Magnant

Theory & Applications of Graphs

A path in an edge-colored graph is properly colored if no two consecutive edges receive the same color. In this survey, we gather results concerning notions of graph connectivity involving properly colored paths.

Dynamic Approach To K-Forcing, Yair Caro, Ryan Pepper

Theory & Applications of Graphs

The k-forcing number of a graph is a generalization of the zero forcing number. In this note, we give a greedy algorithm to approximate the k-forcing number of a graph. Using this dynamic approach, we give corollaries which improve upon two theorems from a recent paper of Amos, Caro, Davila and Pepper [2], while also answering an open problem posed by Meyer [9].

Self-Mappings Of The Quaternionic Unit Ball: Multiplier Properties, Schwarz-Pick Inequality, And Nevanlinna-Pick Interpolation Problem, Daniel Alpay, Vladimir Bolotnikov, Fabrizio Colombo, Irene Sabadini, Fabrizio Colombo

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study several aspects concerning slice regular functions mapping the quaternionic open unit ball B into itself. We characterize these functions in terms of their Taylor coefficients at the origin and identify them as contractive multipliers of the Hardy space H2(B). In addition, we formulate and solve the Nevanlinna-Pick interpolation problem in the class of such functions presenting necessary and sufficient conditions for the existence and for the uniqueness of a solution. Finally, we describe all solutions to the problem in the indeterminate case.

Infinite Product Representations For Kernels And Iteration Of Functions, Daniel Alpay, Palle Jorgensen, Izchak Lewkowicz, Itzik Marziano

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study infinite products of reproducing kernels with view to their use in dynamics (of iterated function systems), in harmonic analysis, and in stochastic processes. On the way, we construct a new family of representations of the Cuntz relations. Then, using these representations we associate a fixed filled Julia set with a Hilbert space. This is based on analysis and conformal geometry of a fixed rational mapping R in one complex variable, and its iterations.

Realizations Of Infinite Products, Ruelle Operators And Wavelet Filters, Daniel Alpay, Palle Jorgensen, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

Using the system theory notion of state-space realization of matrix-valued rational functions, we describe the Ruelle operator associated with wavelet filters. The resulting realization of infinite products of rational functions have the following four features: 1) It is defined in an infinite-dimensional complex domain. 2) Starting with a realization of a single rational matrix-function M, we show that a resulting infinite product realization obtained from M takes the form of an (infinitedimensional) Toeplitz operator with the symbol that is a reflection of the initial realization for M. 3) Starting with a subclass of rational matrix functions, including scalar-valued ones corresponding …

Spectral Theory For Gaussian Processes: Reproducing Kernels, Random Functions, Boundaries, And L2-Wavelet Generators With Fractional Scales, Daniel Alpay

Mathematics, Physics, and Computer Science Faculty Articles and Research

A recurrent theme in functional analysis is the interplay between the theory of positive definite functions, and their reproducing kernels, on the one hand, and Gaussian stochastic processes, on the other. This central theme is motivated by a host of applications, e.g., in mathematical physics, and in stochastic differential equations, and their use in financial models. In this paper, we show that, for three classes of cases in the correspondence, it is possible to obtain explicit formulas which are amenable to computations of the respective Gaussian stochastic processes. For achieving this, we first develop two functional analytic tools. They are: …