
We prove a very natural generalization of the Borsuk-Ulam antipodal theorem and deduce from it, in a very straightforward way, the celebrated result of Alon [1] on splitting necklaces. Alon’s result states that
Two classical theorems about tournaments state that a tournament with no less than eight vertices admits an antidirected Hamiltonian path and an even cardinality tournament with no less than sixteen vertices admits an antidirected Hamiltonian cycle. Sequential algorithms for finding such a path as well as a cycle follow directly from the proofs of the theorems. Unfortunately, these proofs are inherently sequential and cannot be exploited in a parallel context. In this paper, we propose new proofs leading to efficient parallel algorithms.
In this article, we discuss the number of pairwise orthogonal Latin squares and obtain the estimate
In this paper, we present some results on the existence of balanced arrays (B-arrays) with two symbols and of strength four by using some inequalities involving the statistical concepts of skewness and kurtosis. We demonstrate also, through an illustrative example, that in certain situations, the results given here lead to sharper upper bounds on the number of constraints for B-arrays.
If
Then
and the rank of
If
Let
with a unique element
investigation into the admissibility of linear groups, one of the
present authors was recently asked if, for every cyclic group
of even order greater than
answer the above question in the affirmative and we prove the
more general result that every abelian group which has a cyclic
Sylow
bijection.
A directed triple system of order
denoted
admits an automorphism consisting of
is even, or a fixed point and
is odd. We give necessary and sufficient conditions for the
existence of a reverse
A
A graph
let
on
having exactly
when
Recently, we resolved the case
In this paper we show that the complete graph
is not decomposable into three factors of diameter two, thus
resolving a longstanding open problem. This result completes
the solution of decomposition of a complete graph into three
factors, one of which has diameter two and the other factors
have finite diameters.
The edge-integrity of a graph measures the difficulty of breaking it into pieces through the removal of a set of edges, taking into account both the number of edges removed and the size of the largest surviving component. We develop some techniques for bounding, estimating and computing the edge-integrity of products of graphs, paying particular attention to grid graphs.
We describe an algorithm for computing the number
The method described here has been implemented. Numerical data resulting from this implementation are presented at the end of this article.
The core
A
We show that for sufficiently large
If
Motivated by questions about semilattices of ordered compactifications, we study the structure of the lattice
We describe the covering relation of such lattices and characterize “modular” and “semimodular” elements. In particular, we show that the closed equivalence relations on
As a consequence of these results, two compact spaces are homeomorphic if and only if their lattices of closed quasiorders are isomorphic.
Methods of computing fixed points can be regarded as the culmination of many years of mathematical research, starting with Brouwer’s nonconstructive fixed point theorem in 1910. The breakthrough came in 1967 when Scarf succeeded in giving the first constructive proof of Brouwer’s fixed point theorem.
There are now a number of algorithms for computing fixed points using triangulation or primitive sets, based on Scarf’s concept, and complementary pivoting techniques. All these algorithms provide a constructive proof of Sperner’s Lemma for triangulation or a version of Sperner’s Lemma for primitive sets.
It is shown that they have a common combinatorial structure, which can be described, for instance, in terms of maximal chains with respect to a binary relation. This can be the basis for constructing new algorithms of similar type.
This paper studies a special instance of the graph partitioning problem motivated by an application in parallel processing. When a parallel computation is represented by a weighted task graph, we consider the problem of mapping each node in the graph to a processor in a linear array. We focus on a particular type of computation, a grid structured computation (GSC), where the task graph is a grid of nodes.
The general task graph mapping problem is known to be intractable, and thus past research efforts have either proposed heuristics for the general problem or optimally solved a constrained version of the general problem. Our contributions in this paper fall into both categories. We weaken past constraints and optimally solve a less constrained problem than has been solved optimally before and also present and analyze a simple greedy heuristic.
Optimal solutions have been given in the past when one places the contiguity constraint that each partition must consist of entire columns (or rows) of the GSC. We show that a more efficient solution can be found by relaxing the constraints on the partitions to allow parts of consecutive columns to be mapped to a processor; we call this weaker contiguity constraint the part-column constraint.
Our first result is to show that the problem of finding an optimal mapping satisfying the contiguity constraint remains NP-complete, where the contiguity constraint simply requires adjacent nodes to be mapped to the same or adjacent processors. We then design an
Our loosening of past constraints is shown to lead to a forty percent improvement in some cases. Other experimental results compare the proposed heuristic with the optimal algorithm.
Let
1970-2025 CP (Manitoba, Canada) unless otherwise stated.