Discrete Mathematics and Combinatorics Commons^™

Self-Organized Criticality In Biased Activated Random Walk, Joshua Meisel

Dissertations, Theses, and Capstone Projects

We demonstrate many of the conjectured universality and self-organized criticality (SOC) properties of the interacting particle system Activated Random Walk (ARW) in the setting of one-dimensional biased walks, as formulated for instance in Levine and Silvestri’s 2024 survey. Namely, there exists the same limiting critical state for two finite ARW models, as well as for the infinite model as the density approaches its critical value from below. Many of the desired properties hold, including heavy-tailed avalanches, but spatial correlations decay exponentially fast, a deviation from the SOC paradigm. Nonetheless, the obtained decay rate vanishes with the bias. Since the critical …

Quiver Of Affine Monoid Of A Vector Space Over Finite Field, James Junie Chen Cleary

Dissertations, Theses, and Capstone Projects

In this paper, we study the quiver of the complex monoid algebra CAFF(n, q). There are n + 1 maximal subgroups of AFF(n, q), each isomorphic to AGL(k, q) for some 0 ≤ k ≤ n. Every irreducible representation of CAFF(n, q) arises from a character of CAGL(k, q) for a suitable k. Thus, we study two different approaches to classifying the characters of CAGL(k, q). Next, we compute the full quiver Q(CAFF(n, q)). Finally, we show that this quiver is a disjoint union of straight-line paths and that its basic algebra has radical square zero. Hence, it has finite …

Categorical Chain Conditions For Étale Groupoid Algebras, Sunil Philip

Dissertations, Theses, and Capstone Projects

Let R be a unital commutative ring and G an ample groupoid. Using the topology of the groupoid G, Steinberg defined an étale groupoid algebra RG. These étale groupoid algebras generalize various algebras, including group algebras, commutative algebras over a field generated by idempotents, traditional groupoid algebras, Leavitt path algebras, higher-rank graph algebras, and inverse semigroup algebras. Steinberg later characterized the classical chain conditions for étale groupoid algebras. In this work, we characterize categorically noetherian and artinian, locally noetherian and artinian, and semisimple étale groupoid algebras, thereby generalizing existing results for Leavitt path algebras and introducing new results for inverse …

On The Order-Type Complexity Of Words, And Greedy Sidon Sets For Linear Forms, Yin Choi Cheng

Dissertations, Theses, and Capstone Projects

This work consists of two parts. In the first part, we study the order-type complexity of right-infinite words over a finite alphabet, which is defined to be the order types of the set of shifts of said words in lexicographical order. The set of shifts of any aperiodic morphic words whose first letter in the purely-morphic pre-image occurs at least twice in the pre-image has the same order type as Q ∩ (0, 1), Q ∩ (0, 1], or Q ∩ [0, 1). This includes all aperiodic purely-morphic binary words. The order types of uniform-morphic ternary words were also studied, …

Evaluation Of Symmetric Functions And Boolean Functions Over Stochastic Input, Naifeng Liu

Dissertations, Theses, and Capstone Projects

In our daily life, we often face situations where we need to make precise judgments based on initially unknown information, while gathering all the evidence to make informed conclusions can be very costly. In this dissertation, we explore the problem of optimizing the decision-making process under uncertainty, and we focus on problems that can be found in both theoretical computer science and discrete mathematics. The primary goal is to develop approximation algorithms with guaranteed worst-case performance. These algorithms aim to minimize the expected cost of acquiring information necessary for evaluating fundamental functions, such as Boolean and symmetric functions. Furthermore, we …

Fuglede's Conjecture In Some Finite Abelian Groups, Thomas Fallon

Dissertations, Theses, and Capstone Projects

This dissertation thoroughly examines Fuglede's Conjecture within some discrete settings, shedding light on its intricate details. Fuglede's Conjecture establishes a profound connection between the geometric property of being a tiling set and the analytical attribute of being a spectral set. By exploring the conjecture on various discrete settings, this thesis delves into the implications and ramifications of the conjecture, unraveling its implications within the field.

A Stronger Strong Schottky Lemma For Euclidean Buildings, Michael E. Ferguson

Dissertations, Theses, and Capstone Projects

We provide a criterion for two hyperbolic isometries of a Euclidean building to generate a free group of rank two. In particular, we extend the application of a Strong Schottky Lemma to buildings given by Alperin, Farb and Noskov. We then use this extension to obtain an infinite family of matrices that generate a free group of rank two. In doing so, we also introduce an algorithm that terminates in finite time if the lemma is applicable for pairs of certain kinds of matrices acting on the Euclidean building for the special linear group over certain discretely valued fields.

Conflict Dynamics In Scale-Free Networks With Degree Correlations And Hierarchical Structure, Eduardo Jacobo-Villegas, Bibiana Obregón-Quintana, Lev Guzmán-Vargas, Larry S. Liebovitch

Publications and Research

We present a study of the dynamic interactions between actors located on complex networks with scale-free and hierarchical scale-free topologies with assortative mixing, that is, correlations between the degree distributions of the actors. The actor’s state evolves according to a model that considers its previous state, the inertia to change, and the influence of its neighborhood. We show that the time evolution of the system depends on the percentage of cooperative or competitive
interactions. For scale-free networks, we find that the dispersion between actors is higher when all interactions are either cooperative or competitive, while a balanced presence of interactions …

Asymptotic Classes, Pseudofinite Cardinality And Dimension, Alexander Van Abel

Dissertations, Theses, and Capstone Projects

We explore the consequences of various model-theoretic tameness conditions upon the behavior of pseudofinite cardinality and dimension. We show that for pseudofinite theories which are either Morley Rank 1 or uncountably categorical, pseudofinite cardinality in ultraproducts satisfying such theories is highly well-behaved. On the other hand, it has been shown that pseudofinite dimension is not necessarily well-behaved in all ultraproducts of theories which are simple or supersimple; we extend such an observation by constructing simple and supersimple theories in which pseudofinite dimension is necessarily ill-behaved in all such ultraproducts. Additionally, we have novel results connecting various forms of asymptotic classes …

Combinatorial Optimization With Photonics-Inspired Clock Models, Mostafa Honari-Latifpour, Matthew S. Mills, Mohammad-Ali Miri

Publications and Research

NP-hard combinatorial optimization problems are in general hard problems that their computational complexity grows faster than polynomial scaling with the size of the problem. Thus, over the years there has been a great interest in developing unconventional methods and algorithms for solving such problems. Here, inspired by the nonlinear optical process of q-photon down-conversion, in which a photon is converted into q degenerate lower energy photons, we introduce a nonlinear dynamical model that builds on coupled single-variable phase oscillators and allows for efficiently approximating the ground state of the classical q-state planar Potts Hamiltonian. This reduces the exhaustive search in …

Introduction To Discrete Mathematics: An Oer For Ma-471, Mathieu Sassolas

Open Educational Resources

The first objective of this book is to define and discuss the meaning of truth in mathematics. We explore logics, both propositional and first-order , and the construction of proofs, both formally and human-targeted. Using the proof tools, this book then explores some very fundamental definitions of mathematics through set theory. This theory is then put in practice in several applications. The particular (but quite widespread) case of equivalence and order relations is studied with detail. Then we introduces sequences and proofs by induction, followed by number theory. Finally, a small introduction to combinatorics is …

On Communication For Distributed Babai Point Computation, Maiara F. Bollauf, Vinay A. Vaishampayan, Sueli I.R. Costa

Publications and Research

We present a communication-efficient distributed protocol for computing the Babai point, an approximate nearest point for a random vector X∈Rn in a given lattice. We show that the protocol is optimal in the sense that it minimizes the sum rate when the components of X are mutually independent. We then investigate the error probability, i.e. the probability that the Babai point does not coincide with the nearest lattice point, motivated by the fact that for some cases, a distributed algorithm for finding the Babai point is sufficient for finding the nearest lattice point itself. Two different probability models for X …

The “Knapsack Problem” Workbook: An Exploration Of Topics In Computer Science, Steven Cosares

Open Educational Resources

This workbook provides discussions, programming assignments, projects, and class exercises revolving around the “Knapsack Problem” (KP), which is widely a recognized model that is taught within a typical Computer Science curriculum. Throughout these discussions, we use KP to introduce or review topics found in courses covering topics in Discrete Mathematics, Mathematical Programming, Data Structures, Algorithms, Computational Complexity, etc. Because of the broad range of subjects discussed, this workbook and the accompanying spreadsheet files might be used as part of some CS capstone experience. Otherwise, we recommend that individual sections be used, as needed, for exercises relevant to a course in …

Approximation By The K^Lambda Means Of Fourier Series And Conjugate Series Of Functions In H_{Alpha,P}, Ben Landon, Holly Carley, R. N. Mohapatra

Publications and Research

No abstract provided.

Math 220p Foundations Of Mathematics, Nicholas Vlamis

Open Educational Resources

No abstract provided.

On Some Geometry Of Graphs, Zachary S. Mcguirk

Dissertations, Theses, and Capstone Projects

In this thesis we study the intrinsic geometry of graphs via the constants that appear in discretized partial differential equations associated to those graphs. By studying the behavior of a discretized version of Bochner's inequality for smooth manifolds at the cone point for a cone over the set of vertices of a graph, a lower bound for the internal energy of the underlying graph is obtained. This gives a new lower bound for the size of the first non-trivial eigenvalue of the graph Laplacian in terms of the curvature constant that appears at the cone point and the size of …

Some Results In Combinatorial Number Theory, Karl Levy

Dissertations, Theses, and Capstone Projects

The first chapter establishes results concerning equidistributed sequences of numbers. For a given $d\in\mathbb{N}$, $s(d)$ is the largest $N\in\mathbb{N}$ for which there is an $N$-regular sequence with $d$ irregularities. We compute lower bounds for $s(d)$ for $d\leq 10000$ and then demonstrate lower and upper bounds $\left\lfloor\sqrt{4d+895}+1\right\rfloor\leq s(d)< 24801d^{3} + 942d^{2} + 3$ for all $d\geq 1$. In the second chapter we ask if $Q(x)\in\mathbb{R}[x]$ is a degree $d$ polynomial such that for $x\in[x_k]=\{x_1,\cdots,x_k\}$ we have $|Q(x)|\leq 1$, then how big can its lead coefficient be? We prove that there is a unique polynomial, which we call $L_{d,[x_k]}(x)$, with maximum lead coefficient under these constraints and construct an algorithm that generates $L_{d,[x_k]}(x)$.

Solving Algorithmic Problems In Finitely Presented Groups Via Machine Learning, Jonathan Gryak

Dissertations, Theses, and Capstone Projects

Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to polycyclic and metabelian groups that are of interest to non-commutative cryptography.

As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N-tuple neural network models are evaluated for several non-free groups. …

The History Of Algorithmic Complexity, Audrey A. Nasar

Publications and Research

This paper provides a historical account of the development of algorithmic complexity in a form that is suitable to instructors of mathematics at the high school or undergraduate level. The study of algorithmic complexity, despite being deeply rooted in mathematics, is usually restricted to the computer science curriculum. By providing a historical account of algorithmic complexity through a mathematical lens, this paper aims to equip mathematics educators with the necessary background and framework for incorporating the analysis of algorithmic complexity into mathematics courses as early on as algebra or pre-calculus.

Polynomials Occuring In Generating Function Identities For B-Ary Partitions, David Dakota Blair

Graduate Student Publications and Research

Let p_b(n) be the number of integer partitions of n whose parts are powers of b. For each m there is a generating function identity:

f_m(b,q)\sum_{n} p_b(n) q^n = (1-q)^m \sum_{n} p_b(b^m n q)q^n

where n ranges over all integer values. The proof of this identity appears in the doctoral thesis of the author. For more information see http://dakota.tensen.net/2015/rp/.

This dataset is a JSON object with keys m from 1 to 23 whose values are f_m(b,q).

The Minimum Of The Maximum Rectilinear Crossing Numbers Of Small Cubic Graphs, Matthew Alpert, Jens-P. Bode, Elie Feder, Heiko Harborth

Publications and Research

Here we consider the minimum of the maximum rectilin­ear crossing numbers for all d-regular graphs of order n. The case of connected graphs only is investigated also. For d = 3 exact values are determined for n are less than or equal to 12 and some estimations are given in general.

The Maximum Rectilinear Crossing Number Of The Wheel Graph, Elie Feder

Publications and Research

We find and prove the maximum rectilinear crossing number of the wheel graph. First, we illustrate a picture of the wheel graph with many crossings to prove a lower bound. We then prove that this bound is sharp. The treatment is divided into two cases for n even and n odd.

The Maximum Rectilinear Crossing Number Of The Petersen Graph, Elie Feder, Heiko Harborth, Steven Herzberg, Sheldon Klein

Publications and Research

We prove that the maximum rectilinear crossing number of the Petersen graph is 49. First, we illustrate a picture of the Petersen graph with 49 crossings to prove the lower bound. We then prove that this bound is sharp by carefully analyzing the ten Cs's which occur in the Petersen graph and their properties.

The Maximum Rectilinear Crossing Number Of The N Dimensional Cube Graph, Matthew Alpert, Elie Feder, Heiko Harborth, Sheldon Klein

Publications and Research

We find a.nd prove the maximum rectilinear crossing n1.1mber of the three-dimensional cube graph (Q₃). We demonstrate a method of drawing then-cube graph, Q_n., with many crossings, and thus find a lower bound for the maximum rectilinear crossing number of Q_n. We conjecture that this bound is sharp. We also prove an upper bound for the maximum rectilinear crossing number of Q_n.

The Maximum Of The Maximum Rectilinear Crossing Numbers Of D-Regular Graphs Of Order N, Matthew Alpert, Elie Feder, Heiko Harborth

Publications and Research

We extend known results regarding the maximum rectilinear crossing number of the cycle graph (Cn) and the complete graph (Kn ) to the class of general d-regular graphs Rn,d. We present the generalized star drawings of the d-regular graphs Sn,d of order n where n + d ≡ 1 (mod 2) and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of Sn,d for n ≡ d ≡ 0 (mod 2) is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by …

The Orchard Crossing Number Of An Abstract Graph, Elie Feder, David Garber

Publications and Research

.We introduce the Orchard crossing number, which is defined in a similar way to the well-known rectilinear crossing number. We compute the Orchard crossing number for some simple families of graphs. We also prove some properties of this crossing number.

Moreover, we define a variant of this crossing number which is tightly connected to the rectilinear crossing number, and compute it for some simple families of graphs.

Towards The Computation Of The Convex Hull Of A Configuration From Its Corresponding Separating Matrix, Elie Feder, David Garber

Publications and Research

In this paper we cope with the following problem compute the size of the convex hull of a configuration C where the given data is the number of separating lines between any two points of the configuration (where the lines are generated by pairs of other points of the configuration)

We give an algorithm for the case that the convex hull is of size 3 and a partial algorithm and some directions for the case that the convex hull is of size bigger than 3.

Difference Equations, Isoperimetric Inequality And Transience Of Certain Random Walks, Jozef Dodziuk

Publications and Research

No abstract provided.