On distance nonregularity of Preparata codes

It is shown that among all Preparata codes only the code of length 16 is distance regular. An analogous result takes place for Preparata codes after puncturing any coordinate (only the code of length 15 is distance regular).     

On permutation representations of polyhedral groups

We answer affirmatively the following question of Derek Holt: Given integers , can one, in a simple manner, find a finite set and permutations such that has order , has order and has order ? The method of proof enables us to prove more general results (Theorems 2 and 3).

     

Linear optimization over permutation groups

For a permutation group given by a set of generators, the problem of finding “special” group members is NP-hard in many cases, e.g., this is true for the problem of finding a permutation with a minimum number of fixed points or a permutation with a minimal Hamming distance from a given permutation. Many of these problems can be modeled as linear optimization problems over permutation groups. We develop a polyhedral approach to this general problem and derive an exact and practically fast algorithm based on the branch & cut-technique.     

On Regular Orbits of Elements of Classical Groups in Their Permutation Representations

Let H be a simple finite classical group not isomorphic to PSL(n, q) for any n, q. We prove that every cyclic subgroup of H has a regular orbit on every nontrivial permutation H-set.     

Homogeneous covering congruences and subgroup covers

A subgroup cover of the integer lattice in two or more dimensions is a presentation of that lattice as a finite union of proper subgroups, no two of the same index. In an earlier paper, Cochrane and Myerson constructed subgroup covers in two dimensions and asked several questions about other methods of construction and about higher dimensions. We answer those questions.     

Decomposition algorithms for the tree edit distance problem

We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91–102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245–1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies.     

On Permutation Groups of Degree a Product of Two Prime-Powers

We determine finite simple groups which have a subgroup of index with exactly two distinct prime divisors. Then from this we derive a classification of primitive permutation groups of degree a product of two prime-powers.     

On the subgroup index problem in finite groups

We address the subgroup index problem in a given finite subgroup lattice L = ℓ(G) which is P-indecomposable and determine out of the structure of L the existence in G of a subgroup [(D)\tilde]\tilde D invariant for all automorphisms of L, with a cyclic complement R in G and where for any pair X ≤ Y of subgroups of [(D)\tilde]\tilde D the index |Y: X| can be computed using only structural properties of L. As a consequence, we show that in such an L all the terms of the Fitting series of G can be determined, as well as an upper bound of the order of G can be computed out of L as long as G has no cyclic Hall direct factor.     

On the congruence subgroup problem for branch groups

We prove here an energy estimate for the Cauchy problem for hyperbolic equations with double characteristic, which contains both effectively and non-effectively points (see L. Hörmander [3] and R. Melrose [8]) in a unique framework.     

On mean distance and girth

We bound the mean distance in a connected graph which is not a tree in terms of its order n and its girth g. On one hand, we show that the mean distance is at most if g is even and at most if g is odd. On the other hand, we prove that the mean distance is at least unless G is an odd cycle. This resolves two conjectures of AutoGraphiX.     

On the Supersolvability of QCLT-Groups

ＯｎｔｈｅＳｕｐｅｒｓｏｌｖａｂｉｌｉｔｙｏｆＱＣＬＴ－ＧｒｏｕｐｓＷａｎｇＰｉｎｃｈａｏ（王品超）；ＬｕＺａｉｐｉｎｇ（路在平）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＱｕｆｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕｆｕ，Ｓｈａｎｄｏｎｇ，...     

On the editing distance of graphs

An edge‐operation on a graph G is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs , the editing distance from G to is the smallest number of edge‐operations needed to modify G into a graph from . In this article, we fix a graph H and consider Forb(n, H), the set of all graphs on n vertices that have no induced copy of H. We provide bounds for the maximum over all n‐vertex graphs G of the editing distance from G to Forb(n, H), using an invariant we call the binary chromatic number of the graph H. We give asymptotically tight bounds for that distance when H is self‐complementary and exact results for several small graphs H. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:123–138, 2008     

Restrictions on the structure of subgroup lattices of finite alternating and symmetric groups

Let G be a finite alternating or symmetric group. We describe an infinite class of finite lattices, none of which is isomorphic to any interval [H,G] in the subgroup lattice of G.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].