Short proofs for cut-and-paste sorting of permutations

We consider the problem of determining the maximum number of moves required to sort a permutation of [n] using cut-and-paste operations, in which a segment is cut out and then pasted into the remaining string, possibly reversed. We give short proofs that every permutation of [n] can be transformed to the identity in at most ⌊2n/3⌋ such moves and that some permutations require at least ⌊n/2⌋ moves.     

Random walks on finitely structured transfinite networks

A general theory for random walks on transfinite networks whose ranks are arbitrary natural numbers is established herein. In such networks, nodes of higher ranks connect together transfinite networks of lower ranks. The probabilities for transitions through such nodes are obtained as extensions of the Nash-Williams rule for random walks on ordinary infinite networks. The analysis is based on the theory of transfinite electrical networks, but it requires that the transfinite network have a structure that generalizes local-finiteness for ordinary infinite networks. The shorting together of nodes of different ranks are allowed; this complicates transitions through such nodes but provides a considerably more general theory. It is shown that, with respect to any finite set of nodes of any ranks, a transfinite random walk can be represented by an irreducible reversible Makov chain, whose state space is that set of nodes.This work was supported by the National Science Foundation under the grants DMS-9200738 and MIP-9200748.     

The polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.     

用循环图构造可靠通讯网络

本文得到了５度、７～１５度连通循环图的连通度等于其度数的充要条件。从而可用循环图构造可靠通讯网络。     

图与其补图谱半径之间的关系

本文我们将图与其补图结合起来，给出了图与其补图的谱半径所必须满足的两个不等式。     

Tree decompositions of graphs: Saving memory in dynamic programming

We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced “anchor technique” is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.     

The Round Functions of Cryptosystem PGM Generate the Symmetric Group

S. S. Magliveras et al. have described symmetric and public key cryptosystems based on logarithmic signatures (also known as group bases) for finite permutation groups. In this paper we show that if G is a nontrivial finite group which is not cyclic of order a prime, or the square of a prime, then the round (or encryption) functions of these systems, that are the permutations of G induced by the exact-transversal logarithmic signatures (also known as transversal group bases), generate the full symmetric group on G. This answers a question of S. S. Magliveras, D. R. Stinson and Tran van Trung. AMS Classification:94A60, 20B15, 20B20     

Reduced decompositions and permutation patterns

Billey, Jockusch, and Stanley characterized 321-avoiding permutations by a property of their reduced decompositions. This paper generalizes that result with a detailed study of permutations via their reduced decompositions and the notion of pattern containment. These techniques are used to prove a new characterization of vexillary permutations in terms of their principal dual order ideals in a particular poset. Additionally, the combined frameworks yield several new results about the commutation classes of a permutation. In particular, these describe structural aspects of the corresponding graph of the classes and the zonotopal tilings of a polygon defined by Elnitsky that is associated with the permutation.