Signed permutations and the four color theorem

Let σ₁,σ₂ be two permutations in the symmetric group S_n. Among the many sequences of elementary transpositions τ₁,…,τ_r transforming σ₁ into σ₂=τ_rτ₁σ₁, some of them may be signable, a property introduced in this paper. We show that the four color theorem in graph theory is equivalent to the statement that, for any n≥2 and any σ₁,σ₂S_n, there exists at least one signable sequence of elementary transpositions from σ₁ to σ₂. This algebraic reformulation rests on a former geometric one in terms of signed diagonal flips, together with a codification of the triangulations of a convex polygon on n+2 vertices by permutations in S_n.     

Defining sets of extended cyclic codes invariant under the affine group

We describe the defining sets of extended cyclic codes of length pⁿ over a field and over the ring of integers modulo p^e admitting the affine group AGL_m(p^t), n=mt, as a permutation group.     

A generalization of the formulas for intersection numbers of dual polar association schemes and their applications

Dual polar association schemes form an important family of association schemes, whose intersection numbers were computed in [Wan et al., Studies in Finite Geometry and the Construction of Incomplete Block Designs, Science Press, Beijing, 1966 (in Chinese)]. In this paper, we generalize the formulas for the intersection numbers, and introduce their applications to pooling designs, Cartesian authentication codes and vertex-transitive graphs.     

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.     

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.     

Free groups and involutions in the unit group of a group algebra

We study the existence of free groups of rank 2 in the group generated by the involutions in the unit group of a group algebra over a non-absolute field.Received: 25 March 2004     

Group algebra series and coboundary modules

The shift action on the 2-cocycle group Z²(G,C) of a finite group G with coefficients in a finitely generated abelian group C has several useful applications in combinatorics and digital communications, arising from the invariance of a uniform distribution property of cocycles under the action. In this article, we study the shift orbit structure of the coboundary subgroup B²(G,C) of Z²(G,C). The study is placed within a well-known setting involving the Loewy and socle series of a group algebra over G. We prove new bounds on the dimensions of terms in such series. Asymptotic results on the size of shift orbits are also derived; for example, if C is an elementary abelian p-group, then almost all shift orbits in B²(G,C) are maximal-sized for large enough finite p-groups G of certain classes.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

Automorphism groups of comparability and covering graphs

Let G be a group and H a subgroup of G. It is shown that there exists a partially ordered set (X, ) such that G is isomorphic to the group of all automorphisms of the comparability graph of (X, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (X, ). There also exists a partially ordered set (Y, ) such that G is isomorphic to the group of all automorphisms of the covering graph of (Y, ) and such that under this isomorphism H is mapped onto the group of all order-automorphisms of (Y, ). In this representation X and Y can be taken to be finite if G is finite and of the same cardinality as G if G is infinite.     

Twisted descent algebras and the Solomon-Tits algebra

The notion of descent algebra of a bialgebra is lifted to the Barratt-Joyal setting of twisted bialgebras. The new twisted descent algebras share many properties with their classical counterparts. For example, there are twisted analogs of classical Lie idempotents and of the peak algebra. Moreover, the universal twisted descent algebra is equipped with two products and a coproduct, and there is a fundamental rule linking all three. This algebra is shown to be naturally related to the geometry of the Coxeter complex of type A.     

The Number of Cyclic Configurations of Type (v3) and the Isomorphism Problem

A configuration of points and lines is cyclic if it has an automorphism that permutes its points in a full cycle. A closed formula is derived for the number of nonisomorphic connected cyclic configurations of type (v₃), i.e. which have v points and lines, and each point/line is incident with exactly three lines/points. In addition, a Bays–Lambossy type theorem is proved for cyclic configurations if the number of points is a product of two primes or a prime power.     

On the non-existence of linear codes attaining the Griesmer bound

A lower bound on the size of a set K in PG(3, q) satisfying for any plane of PG(3, q), q4 is given. It induces the non-existence of linear [n,4,n + 1 – q ²]-codes over GF(q) attaining the Griesmer bound for .     

The combinatorial Hopf algebra of motivic dissection polylogarithms

We introduce a family of periods of mixed Tate motives called dissection polylogarithms, that are indexed by combinatorial objects called dissection diagrams. The motivic coproduct on the former is encoded by a combinatorial Hopf algebra structure on the latter. This generalizes Goncharov's formula for the motivic coproduct on (generic) iterated integrals. Our main tool is the study of the relative cohomology group corresponding to a bi-arrangement of hyperplanes.     

Covering the hypercube with a bounded number of disjoint snakes

We present a construction of an induced cycle in then-dimensional hypercubeI[n] (n2), and a subgroup _n ofI[n] considered as the group ₂ ⁿ , such that | _n |16 and the induced cycle uses exactly one element of every coset of _n . This proves that for anyn2 the vertices ofI[n] can be covered using at most 16 vertex-disjoint induced cycles.     

The uniqueness of the near hexagon on 729 points

We prove that any regular near hexagon with 729 vertices and lines of size 3 is derived from the ternary Golay code, thus settling the last case in doubt among the regular near hexagons with lines of size 3.     

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 .)