Motivated by questions about semilattices of ordered compactifications, we study the structure of the lattice \(\mathcal{Q}(Y)\) of all closed quasiorders on a (compact) Hausdorff space \(Y\). For example, we show that the meets of coatoms are precisely those quasiorders which make the underlying space totally order-disconnected.
We describe the covering relation of such lattices and characterize “modular” and “semimodular” elements. In particular, we show that the closed equivalence relations on \(Y\) are precisely those upper semimodular elements of \(\mathcal{Q}(Y)\) which are not coatoms, and for \(|Y| \geq 3\), they are just the joins of bi-semimodular elements.
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 \(O(M^2p)\) algorithm (that uses \(O(Mp)\) space) which finds the optimal part-column partitioning of a grid of \(M\) modules to a linear array of \(p\) processors. A simple greedy \(O(M)\) heuristic part-column partitioning algorithm is also presented which performs within a constant factor (two) of the optimal algorithm.
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 \(G\) be a connected graph and let \(u\) and \(v\) be two vertices of \(G\) such that \(d_G(u, v) = 2\). We define their divergence to be: \( \alpha^*(u, v) = \max_{w} \{ |S| \mid \) for each \( w \in N_G(u) \cap N_G(v), S \) is a maximum independent set in \( N_G(w)\) containing \( u \text{ and } v \}.\) It is proved that if for each pair of vertices \(u\) and \(v\) of \(G\) such that \(d_G(u, v) = 2\), \(|N_G(u) \cap N_G(v)| \geq \alpha^*(u, v)\) and if \(\nu(G) \geq 3\), then \(G\) is pancyclic unless \(G\) is \(K_{{\nu}/{2},{\nu}/{2}}\). Several previously known sufficient conditions for pancyclicity follow as corollaries.

We show that the edges of a planar 3-connected graph with \(n\) vertices can be covered by at most \([(n + 1)/{2}]\) cycles. This proves a special case of a conjecture of Bondy that the edges of a 2-connected graph can be covered by at most \((2n – 1)/{3}\) cycles.

In [J. of Combinatorial Theory (B),40(1986),229-230], Fleischner proved that if \(G\) is a \(2\)-edge-connected planar graph and if \(\mathcal{C}_0 = \{C_1, \ldots, C_k\}\) is a collection of edge-disjoint cycles of \(G\), then \(G\) has a cycle double cover \(\mathcal{C}\) that contains \(\mathcal{C}_0\). In this note, we show that this holds also for graphs that do not have a subgraph contractible to \(K_5\).

Given a binary code \(C\), the set \(K\) of all vectors which leave \(C\) invariant under translation is called the kernel of \(C\). The main concern of this paper is the development of an efficient algorithm for computing the kernel of \(C\). We present such an algorithm with runtime \(O(|C| \log |C|)\), which is the best possible.

The intersection problem for a pair of transitive triple systems (or \(2-(v, 3, 1)\) directed designs) was solved by Lindner and Wallis, and independently by H.L. Fu, in 1982-1983. In this paper, we determine the intersection problem for a pair of \(2-(v, 4, 1)\) directed designs.

Let \(H_a^1 = \{v: v \geq a, v \equiv 0,1 \pmod{a}\}\). It is well known that such sets are PBD-closed. Finite bases are found for these sets for \(a = 6, 7,\) and \(8\). At the same time, we improve the result of Mullin in [6] about finite bases of \(H^a = \{v: v \geq a+1, v \equiv 1 \pmod{a}\}\) for \(a = 5\) and \(6\).