Discrete Mathematics and Combinatorics Commons^™

Interpolation By Polynomials With Symmetries, Daniel Alpay, Izchak Lewkowicz

Mathematics, Physics, and Computer Science Faculty Articles and Research

We here specialize the standard matrix-valued polynomial interpolation to the case where on the imaginary axis the interpolating polynomials admit various symmetries: Positive semidefinite, Skew-Hermitian, J- Hermitian, Hamiltonian and others.

The procedure is comprized of three stages, illustrated through the case where on $i\R$ the interpolating polynomials are to be positive semidefinite. We first, on the expense of doubling the degree, obtain a minimal degree interpolating polynomial P(s) which on $i\R$ is Hermitian. Then we find all polynomials Ψ(s), vanishing at the interpolation points which are positive semidefinite on $i\R$. Finally, using the fact that the set of positive semidefinite …

Krein-Langer Factorization And Related Topics In The Slice Hyperholomorphic Setting, Daniel Alpay, Fabrizio Colombo, Irene Sabadini

Mathematics, Physics, and Computer Science Faculty Articles and Research

We study various aspects of Schur analysis in the slice hyperholomorphic setting. We present two sets of results: first, we give new results on the functional calculus for slice hyperholomorphic functions. In particular, we introduce and study some properties of the Riesz projectors. Then we prove a Beurling-Lax type theorem, the so-called structure theorem. A crucial fact which allows to prove our results, is the fact that the right spectrum of a quaternionic linear operator and the point S-spectrum coincide. Finally, we study the Krein-Langer factorization for slice hyperholomorphic generalized Schur functions. Both the Beurling-Lax type theorem and the Krein-Langer …

On The Dynamic Coloring Of Strongly Regular Graphs, Saieed Akbari, Maryam Ghanbari, Sogol Jahanbekam

Faculty Publications

No abstract provided.

Regularity Of Mediatrices In Surfaces, Pilar Herreros, Mario Ponce, J. J. P. Veerman

Mathematics and Statistics Faculty Publications and Presentations

For distinct points p and q in a two-dimensional Riemannian manifold, one defines their mediatrix Lpq as the set of equidistant points to p and q. It is known that mediatrices have a cell decomposition consisting of a finite number of branch points connected by Lipschitz curves. This paper establishes additional geometric regularity properties of mediatrices. We show that mediatrices have the radial linearizability property, which implies that at each point they have a geometrically defined derivative in the branching directions. Also, we study the particular case of mediatrices on spheres, by showing that they are Lipschitz simple closed curves …

Application Of Linear Sequences To Cryptography, Amanda C. Yeates

Honors Theses

Cryptography is the study of a centuries–old technique of secretly transferring information between parties. Linear recurrences were the chosen method of encryption and decryption in the thesis. The Fibonacci sequence, with its Zeckendorf representation, allows for the flexibility of encoding any number desired based on a particular encoding technique used in the film Sherlock Holmes: A Game of Shadows. The main goal is to find other linear recurrences that possess characteristics similar to the Fibonacci sequence to use as suitable substitutes for encoding. Different sequences were analyzed based on a number of criteria. In order for a sequence to be …

Reducibility Of Eulerian Graphs And Digraphs, Akram B. Attar

Applications and Applied Mathematics: An International Journal (AAM)

In this paper the concept of reducibility in graph theory is discussed, and the deletable vertex (edge) in graph (digraph) is defined. The class of graphs (digraphs) ℛ is called vertex (edge) reducible if for any G∈ ℛ either ℛ is the trivial graph (null graph) or it contains a vertex (edge) v such that G-v∈ ℛ. We introduce some classes of graphs (digraphs) which are reducible and others which are not. The vertex reducibility and edge reducibility of Eulerian graphs and Eulerian digraphs have also been studied.

Extremal Results For Peg Solitaire On Graphs, Aaron D. Gray

Electronic Theses and Dissertations

In a 2011 paper by Beeler and Hoilman, the game of peg solitaire is generalized to arbitrary boards. These boards are treated as graphs in the combinatorial sense. An open problem from that paper is to determine the minimum number of edges necessary for a graph with a fixed number of vertices to be solvable. This thesis provides new bounds on this number. It also provides necessary and sufficient conditions for two families of graphs to be solvable, along with criticality results, and the maximum number of pegs that can be left in each of the two graph families.

Packings And Coverings Of Complete Graphs With A Hole With The 4-Cycle With A Pendant Edge, Yan Xia

Electronic Theses and Dissertations

In this thesis, we consider packings and coverings of various complete graphs with the 4-cycle with a pendant edge. We consider both restricted and unrestricted coverings. Necessary and sufficient conditions are given for such structures for (1) complete graphs K_v, (2) complete bipartite graphs K_m,n, and (3) complete graphs with a hole K(v,w).

Lattice Point Counting And Height Bounds Over Number Fields And Quaternion Algebras, Lenny Fukshansky, Glenn Henshaw

CMC Faculty Publications and Research

An important problem in analytic and geometric combinatorics is estimating the number of lattice points in a compact convex set in a Euclidean space. Such estimates have numerous applications throughout mathematics. In this note, we exhibit applications of a particular estimate of this sort to several counting problems in number theory: counting integral points and units of bounded height over number fields, counting points of bounded height over positive definite quaternion algebras, and counting points of bounded height with a fixed support over global function fields. Our arguments use a collection of height comparison inequalities for heights over a number …

Counting The Number Of Squares Reachable In K Knight's Moves., Amanda M. Miller, David L. Farnsworth

Articles

from its initial position on an infinite chessboard are derived. The number of squares reachable in exactly k moves are 1, 8, 32, 68, and 96 for k = 0, 1, 2, 3, and 4, respectively, and 28k – 20 for k ≥ 5. The cumulative number of squares reach- able in k or fever moves are 1, 9, 41, and 109 for k = 0, 1, 2, and 3, respectively, and 14k-squared – 6k + 5 for k ≥ 4. Although these formulas are known, the proofs that are presented are new and more mathematically accessible then preceding proofs.

A Discrete Approach To The Poincare-Miranda Theorem, Connor Thomas Ahlbach

HMC Senior Theses

The Poincare-Miranda Theorem is a topological result about the existence of a zero of a function under particular boundary conditions. In this thesis, we explore proofs of the Poincare-Miranda Theorem that are discrete in nature - that is, they prove a continuous result using an intermediate lemma about discrete objects. We explain a proof by Tkacz and Turzanski that proves the Poincare-Miranda theorem via the Steinhaus Chessboard Theorem, involving colorings of partitions of n-dimensional cubes. Then, we develop a new proof of the Poincare-Miranda Theorem that relies on a polytopal generalization of Sperner's Lemma of Deloera - Peterson - Su. …

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 …

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.

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

Very Cost Effective Partitions In Graphs, Inna Vasylieva

Electronic Theses and Dissertations

For a graph G=(V,E) and a set of vertices S, a vertex v in S is said to be very cost effective if it is adjacent to more vertices in V -S than in S.

A bipartition pi={S, V- S} is called very cost effective if both S and V- S are very cost effective sets. Not all graphs have a very cost effective bipartition, for example, the complete graphs of odd order do not. We consider several families of graphs G, including Cartesian products and cacti graphs, to determine whether G has a very cost effective bipartition.

Peg Solitaire On Trees With Diameter Four, Clayton A. Walvoort

Electronic Theses and Dissertations

In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.

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 Sciences: 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 …