Discrete Mathematics and Combinatorics Commons^™

Chip Firing Games And Riemann-Roch Properties For Directed Graphs, Joshua Z. Gaslowitz

HMC Senior Theses

The following presents a brief introduction to tropical geometry, especially tropical curves, and explains a connection to graph theory. We also give a brief summary of the Riemann-Roch property for graphs, established by Baker and Norine (2007), as well as the tools used in their proof. Various generalizations are described, including a more thorough description of the extension to strongly connected directed graphs by Asadi and Backman (2011). Building from their constructions, an algorithm to determine if a directed graph has Row Riemann-Roch Property is given and thoroughly explained.

Hypergraph Capacity With Applications To Matrix Multiplication, John Lee Thompson Peebles Jr.

HMC Senior Theses

The capacity of a directed hypergraph is a particular numerical quantity associated with a hypergraph. It is of interest because of certain important connections to longstanding conjectures in theoretical computer science related to fast matrix multiplication and perfect hashing as well as various longstanding conjectures in extremal combinatorics.

We give an overview of the concept of the capacity of a hypergraph and survey a few basic results regarding this quantity. Furthermore, we discuss the Lovász number of an undirected graph, which is known to upper bound the capacity of the graph (and in practice appears to be the best such …

Restricted And Unrestricted Coverings Of Complete Bipartite Graphs With Hexagons, Wesley M. Surber

Electronic Theses and Dissertations

A minimal covering of a graph G with isomorphic copies of graph H is a set {H₁, H₂, H₃, ... , H_n} where H_i is isomorphic to H, the vertex set of H_i is a subset of G, the edge set of G is a subset of the union of H_i's, and the cardinality of the union of H_i's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of H_{i …}

Generalizations Of Pascal's Triangle: A Construction Based Approach, Michael Anton Kuhlmann

UNLV Theses, Dissertations, Professional Papers, and Capstones

The study of this paper is based on current generalizations of Pascal's Triangle, both the expansion of the polynomial of one variable and the multivariate case. Our goal is to establish relationships between these generalizations, and to use the properties of the generalizations to create a new type of generalization for the multivariate case that can be represented in the third dimension.

In the first part of this paper we look at Pascal's original Triangle with properties and classical applications. We then look at contemporary extensions of the triangle to coefficient arrays for polynomials of two forms. The first of …

Simulated Annealing Approach To Flow Shop Scheduling, Sadhana Yellanki

UNLV Theses, Dissertations, Professional Papers, and Capstones

Flow Shop Scheduling refers to the process of allotting various jobs to the machines given, such that every job starts to process on a machine n only after it has finished processing on machine n-1, with each job having n operations to be performed one per machine. To find a schedule that leads to the optimal utilization of resources, expects the schedule to finish in a minimum span of time, and also satisfy the optimality criterion set for the related scheduling problem is NP-Hard, if n > 2. In this thesis, we have developed an algorithm adopting a heuristic called Simulated …

Information-Based Physics: An Intelligent Embedded Agent's Guide To The Universe, Kevin H. Knuth

Physics Faculty Scholarship

In this talk, I propose an approach to understanding the foundations of physics by considering the optimal inferences an intelligent agent can make about the universe in which he or she is embedded. Information acts to constrain an agent’s beliefs. However, at a fundamental level, any information is obtained from interactions where something influences something else. Given this, the laws of physics must be constrained by both the nature of such influences and the rules by which we can make inferences based on information about these influences. I will review the recent progress we have made in this direction. This …

The K-Dominating Graph, Ruth Haas, Karen Seyffarth

Mathematics and Statistics: Faculty Publications

Abstract. Given a graph G, the k-dominating graph of G, D_k(G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D_k(G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D_k(G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of …

Generalizing Tanisaki's Ideal Via Ideals Of Truncated Symmetric Functions, Aba Mbirika, Julianna Tymoczko

Mathematics and Statistics: Faculty Publications

Abstract. We define a family of ideals I_h in the polynomial ring Z[_{x1, . . . , xn}] that are parametrized by Hessenberg functions h (equivalently Dyck paths or ample partitions). The ideals I_h generalize algebraically a family of ideals called the Tanisaki ideal, which is used in a geometric construction of permutation representations called Springer theory. To define I_h, we use polynomials in a proper subset of the variables {_{x1, . . . , xn}} that are symmetric under the corresponding permutation subgroup. We call these polynomials truncated symmetric functions and …

Constructions And Enumeration Methods For Cubic Graphs And Trees, Erica R. Gilliland

Undergraduate Honors Thesis Collection

The goal of this thesis is to study two related problems that, in the broadest terms, lie in a branch of mathematics called graph theory. The first problem examines some new techniques for constructing a Hamilton graph of least possible order and having a preassigned girth, and the second concerns the enumeration of a certain type of graphs called trees.

A New Recursion For Three-Column Combinatorial Macdonald Polynomials, Elizabeth Niese

Mathematics Faculty Research

The Hilbert series of the Garsia–Haiman module M_μ can be described combinatorially as the generating function of certain fillings of the Ferrers diagram of μ where μ is an integer partition of n . Since there are n ! fillings that generate , it is desirable to find recursions to reduce the number of fillings that need to be considered when computing combinatorially. In this paper, we present a combinatorial recursion for the case where μ is an n by 3 rectangle. This allows us to reduce the number of fillings under consideration from (3n)! to (3n)!/(3!ⁿn!).

Knight's Tours On 3 X N Chessboards With A Single Square Removed, Amanda M. Miller, David L. Farnsworth

Articles

The following theorem is proved: A knight’s tour exists on all 3 x n chessboards with one square removed unless: n is even, the removed square is (i, j) with i + j odd, n = 3 when any square other than the center square is removed, n = 5, n = 7 when any square other than square (2, 2) or (2, 6) is removed, n = 9 when square (1, 3), (3, 3), (1, 7), (3, 7), (2, 4), (2, 6), (2, 2), or (2, 8) is removed, or n = 11 when square (1, 3), (2, 4), …

A Generalized White Noise Space Approach To Stochastic Integration For A Class Of Gaussian Stationary Increment Processes, Daniel Alpay, Alon Kipnis

Mathematics, Physics, and Computer Science Faculty Articles and Research

Given a Gaussian stationary increment processes, we show that a Skorokhod-Hitsuda stochastic integral with respect to this process, which obeys the Wick-Itô calculus rules, can be naturally defined using ideas taken from Hida’s white noise space theory. We use the Bochner-Minlos theorem to associate a probability space to the process, and define the counterpart of the S-transform in this space. We then use this transform to define the stochastic integral and prove an associated Itô formula.

Representation Formulas For Hardy Space Functions Through The Cuntz Relations And New Interpolation Problems, Daniel Alpay, Palle Jorgensen, Izchak Lewkowicz, Itzik Marziano

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce connections between the Cuntz relations and the Hardy space H2 of the open unit disk D. We then use them to solve a new kind of multipoint interpolation problem in H2, where for instance, only a linear combination of the values of a function at given points is preassigned, rather than the values at the points themselves.

On Discrete Analytic Functions: Products, Rational Functions, And Reproducing Kernels, Daniel Alpay, Palle Jorgensen, Ron Seager, Dan Volok

Mathematics, Physics, and Computer Science Faculty Articles and Research

We introduce a family of discrete analytic functions, called expandable discrete analytic functions, which includes discrete analytic polynomials, and define two products in this family. The first one is defined in a way similar to the Cauchy-Kovalevskaya product of hyperholomorphic functions, and allows us to define rational discrete analytic functions. To define the second product we need a new space of entire functions which is contractively included in the Fock space. We study in this space some counterparts of Schur analysis.

Pontryagin De Branges-Rovnyak Spaces Of Slice Hyperholomorphic Functions, Daniel Alpay, Fabrizio Colombo, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study reproducing kernel Hilbert and Pontryagin spaces of slice hyperholomorphic functions which are analogs of the Hilbert spaces of analytic functions introduced by de Branges and Rovnyak. In the first part of the paper we focus on the case of Hilbert spaces, and introduce in particular a version of the Hardy space. Then we define Blaschke factors and Blaschke products and we consider an interpolation problem. In the second part of the paper we turn to the case of Pontryagin spaces. We first prove some results from the theory of Pontryagin spaces in the quaternionic setting and, in particular, …

Chromatic Bounds On Orbital Chromatic Roots, Dae Hyun Kim, Alexander H. Mun, Mohamed Omar

All HMC Faculty Publications and Research

Given a group G of automorphisms of a graph Γ, the orbital chromatic polynomial OPΓ,G(x) is the polynomial whose value at a positive integer k is the number of orbits of G on proper k-colorings of Γ. In \cite{Cameron}, Cameron et. al. explore the roots of orbital chromatic polynomials, and in particular prove that orbital chromatic roots are dense in R, extending Thomassen's famous result (see \cite{Thomassen}) that chromatic roots are dense in [32/27,∞). Cameron et al \cite{Cameron} further conjectured that the real roots of the orbital chromatic polynomial of any graph are bounded above by the largest real root …

Billey's Formula In Combinatorics, Geometry, And Topology, Julianna Tymoczko

Mathematics and Statistics: Faculty Publications

In this expository paper we describe a powerful combinatorial formula and its implications in geometry, topology, and algebra. This formula first appeared in the appendix of a book by Andersen, Jantzen, and Soergel. Sara Billey discovered it independently five years later, and it played a prominent role in her work to evaluate certain polynomials closely related to Schubert polynomials. Billey's formula relates many pieces of Schubert calculus: the geometry of Schubert varieties, the action of the torus on the flag variety, combinatorial data about permutations, the cohomology of the flag variety and of the Schubert varieties, and the combinatorics of …

Topological Convolution Algebras, Daniel Alpay, Guy Salomon

Mathematics, Physics, and Computer Science Faculty Articles and Research

In this paper we introduce a new family of topological convolution algebras of the form ⋃p∈NL2(S,μp), where S is a Borel semi-group in a locally compact group G, which carries an inequality of the type ∥f∗g∥p≤Ap,q∥f∥q∥g∥p for p>q+d where d pre-assigned, and Ap,q is a constant. We give a sufficient condition on the measures μp for such an inequality to hold. We study the functional calculus and the spectrum of the elements of these algebras, and present two examples, one in the setting of non commutative stochastic distributions, and the other related to Dirichlet series.

Subset Non Associative Semirings, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

In this book for the first time we introduce the notion of subset non associative semirings. It is pertinent to keep on record that study of non associative semirings is meager and books on this specific topic is still rare. Authors have recently introduced the notion of subset algebraic structures. The maximum algebraic structure enjoyed by subsets with two binary operations is just a semifield and semiring, even if a ring or a field is used. In case semigroups or groups are used still the algebraic structure of the subset is only a semigroup. To construct a subset non associative …

Convex Cones Of Generalized Positive Rational Functions And Nevanlinna-Pick Interpolation, Daniel Alpay, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

Scalar rational functions with a non-negative real part on the right half plane, called positive, are classical in the study of electrical networks, dissipative systems, Nevanlinna-Pick interpolation and other areas. We here study generalized positive functions, i.e with a non-negative real part on the imaginary axis. These functions form a Convex Invertible Cone, cic in short, and we explore two partitionings of this set: (i) into (infinitely many non-invertible) convex cones of functions with prescribed poles and zeroes in the right half plane and (ii) each generalized positive function can be written as a sum of even and odd parts. …