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.     

A lower bound for the recognition of digraph properties

The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case, Aanderaa and Rosenberg conjectured that there is a constant such that every digraph property which is monotone (not destroyed by the deletion of edges) and nontrivial (holds for some but not all digraphs) has complexity at leastv ² wherev is the number of nodes in the digraph. This conjecture was proved by Rivest and Vuillemin and a lower bound ofv ²/4–o(v ²) was subsequently found by Kahn, Saks, and Sturtevant. Here we show a lower bound ofv ²/2–o(v ²). We also prove that a certain class of monotone, nontrivial bipartite digraph properties is evasive (requires that every entry in the adjacency matrix be examined in the worst case).     

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.     

Connected graphs containing a given connected graph as a unique greatest common subgraph

Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

On graphical partitions

An integer partition {₁,₂,..., _v } is said to be graphical if there exists a graph with degree sequence _i . We give some results corcerning the problem of deciding whether or not almost all partitions of even integer are non-graphical. We also give asymptotic estimates for the number of partitions with given rank.     

On combinatorial properties of spheres in euclidean spaces

For λ>√2 there exists a triangle-free graphG such that for nod canG be imbedded into thed-dimensional unit sphere with two points joined if and only if their distance is >λ.     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

On the lattice formed by all normal subloops of a finite loop

All normal subloops of a loopG form a modular latticeL _n (G). It is shown that a finite loopG has a complemented normal subloop lattice if and only ifG is a direct product of simple subloops. In particular,L _n (G) is a Boolean algebra if and only if no two isomorphic factors occurring in a decomposition ofG are abelian groups. The normal subloop lattice of a finite loop is a projective geometry if and only ifG is an elementary abelianp-group for some primep.     

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.     

The existence of Room squares

The authors give a condensed proof of the existence of Room squares for positive odd sides except 3 and 5. Some areas of current research on Room squares are also discussed.Aequationes Mathematicae launches a systematic program of expository papers. We will endeavour to publish at least one in every volume.     

Finite digraphs with given regular automorphism groups

With five exceptions, every finite regular permutation group occurs as the automorphism group of a digraph.One of the corollaries: given a finite groupG of ordern, there is a commutative semigroupS of order 2n+2 such that AutSG. The problem whether a latticeL of order Cn with AutLG exists (for some constantC), remains open.     

Semilinear representations of PGL

Let L be the function field of a projective space over an algebraically closed field k of characteristic zero, and H be the group of projective transformations. An H-sheaf on is a collection of isomorphisms for each g ∈ H satisfying the chain rule. We construct, for any n > 1, a fully faithful functor from the category of finite-dimensional L-semilinear representations of H extendable to the semigroup End(L/k) to the category of coherent H-sheaves on The paper is motivated by a study of admissible representations of the automorphism group G of an algebraically closed extension of k of countable transcendence degree undertaken in [4]. The semigroup End(L/k) is considered as a subquotient of G, hence the condition on extendability. In the appendix it is shown that, if is either H, or a bigger subgroup in the Cremona group (generated by H and a certain pair of involutions), then any semilinear of degree one is an integral L-tensor power of It is also shown that this bigger subgroup has no non-trivial representations of finite degree if n > 1.     

Rédei-Funktionen für Zweierpotenzen

L. Rédei has introduced in 1946 a class of rational functions over finite fields of orderp ^t –p being an odd prime — and has proved some interesting results on permutations which are induced by these functions. Recently, similar results have been found for factor rings of the integers of orderp ^t ; moreover, these functions have been applied to construct public key cryptosystems. In this paper we consider functions of Rédei type over finite fields and factor rings of the integers of order 2 ^t . We show that most of the results for oddp also hold in this case.

     

Teilmengengraphen und projektive Räume

Ohne Zusammenfassung

---

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

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.     

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

Comparability graphs of lattices

A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N₀). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain.