Discrete Mathematics and Combinatorics Commons^™

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 …

Coloring The Square Of Planar Graphs Without 4-Cycles Or 5-Cycles, Robert Jaeger

Theses and Dissertations

The famous Four Color Theorem states that any planar graph can be properly colored using at most four colors. However, if we want to properly color the square of a planar graph (or alternatively, color the graph using distinct colors on vertices at distance up to two from each other), we will always require at least \Delta + 1 colors, where \Delta is the maximum degree in the graph. For all \Delta, Wegner constructed planar graphs (even without 3-cycles) that require about \frac{3}{2} \Delta colors for such a coloring.

To prove a stronger upper bound, we consider only planar graphs …

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.

Domination Numbers Of Semi-Strong Products Of Graphs, Stephen R. Cheney

Theses and Dissertations

This thesis examines the domination number of the semi-strong product of two graphs G and H where both G and H are simple and connected graphs. The product has an edge set that is the union of the edge set of the direct product of G and H together with the cardinality of V(H), copies of G. Unlike the other more common products (Cartesian, direct and strong), the semi-strong product is neither commutative nor associative.

The semi-strong product is not supermultiplicative, so it does not satisfy a Vizing like conjecture. It is also not submultiplicative so it shares these two …

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 …

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.