超立方体Q_n的传递剖分

一个图的传递剖分是它的边集的一个划分,且满足图的一个自同构群在其划分后的各个部分组成的集合上作用是传递的.决定了超立方体Q_n的所有G-传递剖分,其中G为Q_n的全自同构群.     

Constructing Homogeneous Factorisations of Complete Graphs and Digraphs

 A homogeneous factorisation of a complete graph K _n is a partition of the edge set that is invariant under a subgroup G of S _n such that G is transitive on the parts of the partition and induces a vertex-transitive automorphism group on the graph corresponding to each part. A product construction is given for such factorisations. Received: October, 2001 Final version received: May 17, 2002     

2-Spreads and Transitive and Orthogonal 2-Parallelisms of PG(5, 2)

A 2-spread is a set of two-dimensional subspaces of PG(d, q), which partition the point set. We establish that up to equivalence there exists only one 2-spread of PG(5, 2). The order of the automorphism group preserving it is 10584. A 2-parallelism is a partition of the set of two-dimensional subspaces by 2-spreads. There is a one-to-one correspondence between the 2-parallelisms of PG(5, 2) and the resolutions of the 2-(63,7,15) design of the points and two-dimensional subspaces. Sarmiento (Graphs and Combinatorics 18(3):621–632, 2002) has classified 2-parallelisms of PG(5, 2), which are invariant under a point transitive cyclic group of order 63. We classify 2-parallelisms with automorphisms of order 31. Among them there are 92 2-parallelisms with full automorphism group of order 155, which is transitive on their 2-spreads. Johnson and Montinaro (Results Math 52(1–2):75–89, 2008) point out that no transitive t-parallelisms of PG(d, q) have been constructed for t > 1. The 92 transitive 2-parallelisms of PG(5, 2) are then the first known examples. We also check them for mutual orthogonality and present a set of ten mutually orthogonal resolutions of the geometric 2-(63,7,15) design.     

On tangentially transitive projective planes

The existence of Baer collineations in a projective plane is related to the existence of desargues-like configurations. The plane of order four is characterized as the only finite plane that possesses a Baer subplane partition into tangentially transitive Baer subplanes which is preserved by each of the tangentially transitive groups. It is shown that a finite projective plane has either no or one tangentially transitive Baer subplane or is partially transitive of Hughes type (4, m), (5, m) or (6, m) for some m. The Lenz-Barlotti classes which contain a finite plane which is not a translation plane nor its dual and which possesses a tangentially transitive Baer subplane are shown to be classes I.1 and II.1.     

Rank 3 Transitive Decompositions of Complete Multipartite Graphs

A transitive decomposition of a graph is a partition of the edge or arc set giving a set of subgraphs which are preserved and permuted transitively by a group of automorphisms of the graph. This paper deals with transitive decompositions of complete multipartite graphs preserved by an imprimitive rank 3 permutation group. We obtain a near-complete classification of these when the group in question has an almost simple component.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Linear systems with removable base loci

Abstract

We develop several local approaches for the three classes of finite groups: T-groups (normality is a transitive relation) and PT-groups (permutability is a transitive relation) and PST-groups (S-permutability is a transitive relation). Here a subgroup of a finite group G is S-permutable if it permutes with all the Sylow subgroup of G.     

Finite 2‐Distance Transitive Graphs

A noncomplete graph Γ is said to be (G, 2)‐distance transitive if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set of Γ, and for any vertex u of Γ, the stabilizer is transitive on the sets of vertices at distances 1 and 2 from u. This article investigates the family of (G, 2)‐distance transitive graphs that are not (G, 2)‐arc transitive. Our main result is the classification of such graphs of valency not greater than 5. We also prove several results about (G, 2)‐distance transitive, but not (G, 2)‐arc transitive graphs of girth 4.     

Structure of some ℤ-graded lie superalgebras of vector fields

In this paper we classifyℤ-graded transitive Lie superalgebras with prescribed nonpositive parts listed in [K2]. The classification of infinite-dimensional simple linearly compact Lie superalgebras given in [K2] is based on this result. We also study the structure of the exceptionalℤ-graded transitive Lie superalgebras and give their geometric realization. Dedicated to the memory of Claude Chevalley Partially supported by NSC grant 88-2115-M006-013 of the ROC Partially supported by NSF grant DMS-9622870 An erratum to this article is available at .     

On a conjecture of Brualdi and Shen on block transitive tournaments

The following conjecture of Brualdi and Shen is proven in this paper: let n be partitioned into natural numbers no one of which is greater than (n + 1) / 2. Then, given any sequence of wins for the players of some tournament among n players, there is a partition of the players into blocks with cardinalities given by those numbers, and a tournament with the given sequence of wins, that is transitive on the players within each block. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 215–230, 2003     

Polarity and transitive parabolic unitals in translation planes of odd order

A parabolic unital of a translation plane is called transitive, if the collineation group G fixing fixes the point at infinity of and acts transitively on the affine points of . It has been conjectured that if a transitive parabolic unital consists of the absolute points of a unitary polarity in a commutative semi-field plane, then the sharply transitive normal subgroupK of G is not commutative. So far, this has been proved for commutative twisted field planes of odd square order, see [1],[5]. Here we prove this conjecture for commutative Dickson planes. Received 14 May 2001.     

Markov partitions for anosov flows onn-dimensional manifolds

In this work we construct a Markov partition for transitive Anosov flows, such that the measure of the boundary of the partition is zero. Symbolic dynamics for these flows is also developed.     

The group PSL(2,q) is not the multiplication group of a loop

ABSTRACT

We introduce the notion of weak transitivity for torsion-free abelian groups. A torsion-free abelian group G is called weakly transitive if for any pair of elements x, y ∈ G and endomorphisms ?, ψ ∈ End(G) such that x? = y, yψ = x, there exists an automorphism of G mapping x onto y. It is shown that every suitable ring can be realized as the endomorphism ring of a weakly transitive torsion-free abelian group, and we characterize up to a number-theoretical property the separable weakly transitive torsion-free abelian groups.     

Realizing finite edge‐transitive orientable maps

J.E. Graver and M.E. Watkins, Memoirs Am. Math. Soc. 126 (601) ( 5 ) established that the automorphism group of an edge‐transitive, locally finite map manifests one of exactly 14 algebraically consistent combinations (called types) of the kinds of stabilizers of its edges, its vertices, its faces, and its Petrie walks. Exactly eight of these types are realized by infinite, locally finite maps in the plane. H.S.M. Coxeter (Regular Polytopes, 2nd ed., McMillan, New York, 1963) had previously observed that the nine finite edge‐transitive planar maps realize three of the eight planar types. In the present work, we show that for each of the 14 types and each integer n ≥ 11 such that n ≡ 3,11 (mod 12), there exist finite, orientable, edge‐transitive maps whose various stabilizers conform to the given type and whose automorphism groups are (abstractly) isomorphic to the symmetric group Sym(n). Exactly seven of these types (not a subset of the planar eight) are shown to admit infinite families of finite, edge‐transitive maps on the torus, and their automorphism groups are determined explicitly. Thus all finite, edge‐transitive toroidal maps are classified according to this schema. Finally, it is shown that exactly one of the 14 types can be realized as an abelian group of an edge‐transitive map, namely, as ?_n × ?₂ where n ≡ 2 (mod 4). © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 1–34, 2001     

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

Partitions and orientations of the Rado graph

We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs are the edgeless graph, the random tournament, the transitive tournaments of order type  , and two orientations of the Rado graph: the random oriented graph, and a newly found random acyclic oriented graph.

     

A Family of Non-quasiprimitive Graphs Constructed From PSU3（q） Where q Is Odd

Let Г be a simple connected graph and let G be a group of automorphisms of Г. Г is said to be （G, 2）-arc transitive if G is transitive on the 2-arcs of Г. It has been shown that there exists a family of non-quasiprimitive （PSU3（q）, 2）-arc transitive graphs where q = 2^3m with m an odd integer. In this paper we investigate the case where q is an odd prime power.     

Finding Skew Partitions Efficiently

A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts A, B, C, D such that there are all possible edges between A and B and no edges between C and D. We present a polynomial-time algorithm for testing whether a graph admits a skew partition. Our algorithm solves the more general list skew partition problem, where the input contains, for each vertex, a list containing some of the labels A, B, C, D of the four parts. Our polynomial-time algorithm settles the complexity of the original partition problem proposed by Chvátal in 1985 and answers a recent question of Feder, Hell, Klein, and Motwani.