Partial vexillarity and bigrassmannian permutations

We define two closely related notions of degree for permutation patterns of type 2143. These give rise to classes of “m-vexillary elements” in the symmetric group. Using partitions, the Ehresmann–Bruhat partial order, and sets constructed from permutation inversions, we characterize the m-vexillary elements. We relate the maximal bigrassmannian permutations in the (Ehresmann–Bruhat) order ideal generated by any given m-vexillary element w to the maximal rectangles contained in the shape of w.     

On the sharpness of a theorem of B. segre

The theorem of B. Segre mentioned in the title states that a complete arc of PG(2,q),q even which is not a hyperoval consists of at mostq−√q+1 points. In the first part of our paper we prove this theorem to be sharp forq=s ² by constructing completeq−√q+1-arcs. Our construction is based on the cyclic partition of PG(2,q) into disjoint Baer-subplanes. (See Bruck [1]). In his paper [5] Kestenband constructed a class of (q−√q+1)-arcs but he did not prove their completeness. In the second part of our paper we discuss the connections between Kestenband’s and our constructions. We prove that these constructions result in isomorphic (q−√q+1)-arcs. The proof of this isomorphism is based on the existence of a traceorthogonal normal basis in GF(q ³) over GF(q), and on a representation of GF(q)³ in GF(q ³)³ indicated in Jamison [4].     

On the dual canonical and Kazhdan-Lusztig bases and 3412-, 4231-avoiding permutations

Using Du’s characterization of the dual canonical basis of the coordinate ring O(GL(n,C)), we express all elements of this basis in terms of immanants. We then give a new factorization of permutations w avoiding the patterns 3412 and 4231, which in turn yields a factorization of the corresponding Kazhdan-Lusztig basis elements of the Hecke algebra H_n(q). Using the immanant and factorization results, we show that for every totally nonnegative immanant and its expansion with respect to the basis of Kazhdan-Lusztig immanants, the coefficient d_w must be nonnegative when w avoids the patterns 3412 and 4231.     

Flag transitive planes of dimension four over GF(3)

Two non desarguesian flag transitive planes of order 3⁴ whose Kernel is GF(3) are constructed. These planes are distinct from the planes of the same order contained in the class constructed by Narayana Rao M. L. (Proceedings of American Mathematical Society 39 (1973) 51–56) and Ebert, G.L. and Baker, R. (Enumeration of two dimensional Flag-Transitive planes, Algebras, Groups and Geometries 3 (1985) 248–257). The Flag Transitive group modulo the scalar collineations of these planes is generated by two elements and is of order 328.     

The k-orbit reconstruction and the orbit algebra

Let (G, W) be a permutation group on a finite set W = {w ₁,..., w _n}. We consider the natural action of G on the set of all subsets of W. Let h ₀, h ₁,..., h _N be the orbits of this action. For each i, 1 i N, there exists k, 1 k n, such that h _i is a set of k-element subsets of W. In this case h _i is called a symmetrized k-orbit of the group (G, W) or simply a k-orbit. With a k-orbit h _i we associate a multiset H(h _i ) = % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyykJeoaaa!3690!\[\langle \]h _i ⁽¹⁾, h _i ⁽²⁾,..., h _i ^(k)% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOkJepaaa!36A1!\[\rangle \] of its (k – 1)-suborbits. Orbits h _i and h _j are called equivalent if H(h _i ) = H(h _j ). An orbit is reconstructible if it is equivalent to itself only. The paper concerns the k-orbit reconstruction problem and its connections with different problems in combinatorics. The technique developed is based on the notion of orbit and co-orbit algebras associated with a given permutation group (G, W).     

Toward a language theoretic proof of the four color theorem

This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.     

An arctic circle theorem for Groves

In earlier work, Jockusch, Propp, and Shor proved a theorem describing the limiting shape of the boundary between the uniformly tiled corners of a random tiling of an Aztec diamond and the more unpredictable ‘temperate zone’ in the interior of the region. The so-called arctic circle theorem made precise a phenomenon observed in random tilings of large Aztec diamonds.Here we examine a related combinatorial model called groves. Created by Carroll and Speyer as combinatorial interpretations for Laurent polynomials given by the cube recurrence, groves have observable frozen regions which we describe precisely via asymptotic analysis of a generating function. Our approach also provides another way to prove the arctic circle theorem for Aztec diamonds.     

Search for properties of the missing Moore graph

In the degree-diameter problem, the only extremal graph the existence of which is still in doubt is the Moore graph of order 3250, degree 57 and diameter 2. It has been known that such a graph cannot be vertex-transitive. Also, certain restrictions on the structure of the automorphism group of such a graph have been known in the case when the order of the group is even. In this paper we further investigate symmetries and structural properties of the missing Moore (57, 2)-graph(s) with the help of a combination of spectral, group-theoretic, combinatorial, and computational methods. One of the consequences is that the order of the automorphism group of such a graph is at most 375.     

Teilmengengraphen und projektive Räume

Ohne Zusammenfassung

---

Herrn Professor Dr. Janos Aczél zum 60. Geburtstag gewidmet     

On infinite tournaments with regular automorphism groups

Atournament regular representation (TRR) of an abstract groupG is a tournamentT whose automorphism group is isomorphic toG and is a regular permutation group on the vertices ofT. L. Babai and W. Imrich have shown that every finite group of odd order exceptZ ₃ ×Z ₃ admits a TRR. In the present paper we give several sufficient conditions for an infinite groupG with no element of order 2 to admit a TRR. Among these are the following: (1)G is a cyclic extension byZ of a finitely generated group; (2)G is a cyclic extension byZ _2n+1 of any group admitting a TRR; (3)G is a finitely generated abelian group; (4)G is a countably generated abelian group whose torsion subgroup is finite.     

A class of d-dimensional flag transitive translation planes

Journal of Geometry -     

An extension theorem for D-normal spaces

A second countable developable T₁-space $\text{D}$₁ is defined which has the following properties: (1) $\text{D}$₁ is an absolute extensor for the class of perfect spaces. (2) $\text{D}$₁^?₀ is a universal space for second countable developable T₁-spaces.     

Almost Covers Of 2-Arc Transitive Graphs

Let be a G-symmetric graph whose vertex set admits a nontrivial G-invariant partition with block size v. Let be the quotient graph of relative to and [B,C] the bipartite subgraph of induced by adjacent blocks B,C of . In this paper we study such graphs for which is connected, (G, 2)-arc transitive and is almost covered by in the sense that [B,C] is a matching of v-1 2 edges. Such graphs arose as a natural extremal case in a previous study by the author with Li and Praeger. The case K _v+1 is covered by results of Gardiner and Praeger. We consider here the general case where K _v+1, and prove that, for some even integer n 4, is a near n-gonal graph with respect to a certain G-orbit on n-cycles of . Moreover, we prove that every (G, 2)-arc transitive near n-gonal graph with respect to a G-orbit on n-cycles arises as a quotient of a graph with these properties. (A near n-gonal graph is a connected graph of girth at least 4 together with a set of n-cycles of such that each 2-arc of is contained in a unique member of .)     

Some basic properties of planar Singer groups

A planar Singer group is a collineation group of a finite (in this article) projective plane acting regularly on the points of the plane. Theorem 1 gives a characterization of abelian planar Singer groups. This leads to a necessary and sufficient condition for an inner automorphism to be a multiplier. The Sylow 2-structure of a multiplier group and some of its consequences are given in Theorem 3. One important result in studying multipliers of an abelian Singer group is the existence of a common fixed line. We extend this to an arbitrary planar Singer group in Theorem 4. Theorem 5 studies the order of an abelian group of multiplers. If this order equals to the order of the plane plus 1, then the number of points of the plane is a prime. If this order is odd, then it is at most the planar order plus 1.Partially supported by a NSA grant.     

Pfaffian structures and critical problems in finite symplectic spaces

Just as matroids abstract the algebraic properties of determinants in a vector space, Pfaffian structures abstract the algebraic properties of Pfaffians or skew-symmetric determinants in a symplectic space (that is, a vector space with an alternating bilinear form). This is done using an exchange-augmentation axiom which is a combinatorial version of a Laplace expansion or straightening identity for Pfaffians. Using Pfaffian structures, we study a symplectic analogue of the classical critical problem: given a setS of non-zero vectors in a non-singular symplectic spaceV of dimension2m, find its symplectic critical exponent, that is, the minimum of the set {m?dim(U):U∩S=0}, whereU ranges over all the (totally) isotropic subspaces disjoint fromS. In particular, we derive a formula for the number of isotropic subspaces of a given dimension disjoint from the setS by Möbius inversion over the order ideal of isotropic flats in the lattice of flats of the matroid onS given by linear dependence. This formula implies that the symplectic critical exponent ofS depends only on its matroid and Pfaffian structure; however, it may depend on the dimension of the symplectic spaceV.     

Arc-transitive digraphs with quasiprimitive local actions

Let Γ be a finite G-vertex-transitive digraph. The in-local action of $(\mathrm{\Gamma },G)$ is the permutation group $L_{?}$ induced by a vertex-stabiliser on the set of in-neighbours of the corresponding vertex. The out-local action$L_{+}$ is defined analogously. Note that $L_{?}$ and $L_{+}$ may not be isomorphic. We thus consider the problem of determining which pairs $(L_{?},L_{+})$ are possible. We prove some general results, but pay special attention to the case when $L_{?}$ and $L_{+}$ are both quasiprimitive. (Recall that a permutation group is quasiprimitive if each of its nontrivial normal subgroups is transitive.) Along the way, we prove a structural result about pairs of finite quasiprimitive groups of the same degree, one being (abstractly) isomorphic to a proper quotient of the other.     

Matrices with prescribed row,column and block sums

The main result of the paper is Theorem 1. It concerns the sets of integral symmetric matrices with given block partition and prescribed row, column and block sums. It is shown that by interchanges preserving these sums we can pass from any two matrices, one from each set, to the other two ones falling close together as much as possible. One of the direct corollaries of Theorem 1 is substantiating the fact that any realization ofr-graphical integer-pair sequence can be obtained from any other one byr-switchings preserving edge degrees. This result is also of interest in connection with the problem of determinings-complete properties. In the special cases Theorem 1 includes a number of well-known results, some of which are presented.