Discrete Mathematics and Combinatorics Commons^™

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 …

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 …

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 …

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.

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.

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.