Invariants for group algebras of Abelian groups

LetF be a field of characteristicp>0 and letG be an arbitrary abelian group written multiplicatively withp-basis subgroup denoted byB. The first main result of the present paper is thatB is an isomorphism invariant of theF-group algebraFG. In particular, thep-local algebraically compact groupG can be retrieved fromFG. Moreover, for the lower basis subgroupB ₁ of thep-componentG _p it is shown thatG _p/B_l is determined byFG. Besides, ifH is (p-)high inG, thenG _p/H_p andH ^{p n}[p] for ℕ₀ are structure invariants forFG, andH[p] as a valued vector space is a structural invariant forN ₀ G, whereN _p is the simple field ofp-elements. Next, presume thatG isp-mixed with maximal divisible subgroupD. ThenD andF(G/D) are functional invariants forFG. The final major result is that the relative Ulm-Kaplansky-Mackeyp-invariants ofG with respect to the subgroupC are isomorphic invariants of the pair (FG, FC) ofF-algebras. These facts generalize and extend analogous in this aspect results due to May (1969), Berman-Mollov (1969) and Beers-Richman-Walker (1983). As a finish, some other invariants for commutative group algebras are obtained.     

Symmetric edge-decompositions of hypercubes

We call a set of edgesE of the n-cubeQ _n a fundamental set for Q _n if for some subgroupG of the automorphism group ofQ _n , theG-translates ofE partition the edge set ofQ _n .Q _n possesses an abundance of fundamental sets. For example, a corollary of one of our main results is that if |E| =n and the subgraph induced byE is connected, then if no three edges ofE are mutually parallel,E is a fundamental set forQ _n . The subgroupG is constructed explicitly. A connected graph onn edges can be embedded intoQ _n so that the image of its edges forms such a fundamental set if and only if each of its edges belongs to at most one cycle.We also establish a necessary condition forE to be a fundamental set. This involves a number-theoretic condition on the integersa _j (E), where for 1 j n, a _j (E) is the number of edges ofE in thej ^th direction (i.e. parallel to thej ^th coordinate axis).     

Reduktion von Präzedenzstrukturen

Zusammenfassung Es wird zunächst der Begriff des (transitiv) irreduziblen KernsG _* eines gerichteten GraphenG eingeführt und einige Eigenschaften von irreduziblen Kernen hergeleitet. — Es wird insbesondere gezeigt, daß mit höchstens 0(n ³) elementaren Rechenoperationen die Bestimmung eines Kernes eines beliebigen gerichteten Graphen mitn Ecken möglich ist. — Für Ablaufprobleme zeigt dieses Resultat, daß höchstens 0(n ³) Operationen notwendig sind, um alle redundanten Nebenbedingungen zu eliminieren.

---

Summary A (transitive) irreducible kernelG _* of a directed graphG is introduced as a partial graph ofG, which has the same transitive closure asG while no proper subgraph ofG _* has this property. — The author shows that at most 0(n ³) elementary operations are necessary to obtain a kernel of an arbitrary graph wheren is the number of vertices ofG. In the case of scheduling problems this result shows that at most 0(n ³) operations are needed to eliminate all redundant constraints.

     

Can visibility graphs Be represented compactly?

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graphG, a familyG={G ₁,G ₂,...,G _k } is called aclique cover ofG if (i) eachG _i is a clique or a bipartite clique, and (ii) the union ofG _i isG. The size of the clique coverG is defined as ∑ _i=1 ^k n _i , wheren _i is the number of vertices inG _i . Our main result is that there are visibility graphs ofn nonintersecting line segments in the plane whose smallest clique cover has size Ω(n ²/log² n). An upper bound ofO(n ²/logn) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of sizeO(nlog³ n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n logn). The work by the first author was supported by National Science Foundation Grant CCR-91-06514. The work by the second author was supported by a USA-Israeli BSF grant. The work by the third author was supported by National Science Foundation Grant CCR-92-11541.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

The structure of injective covers of special modules

In this paper, we prove that the injective cover of theR-moduleE(R/B)/R/B for a prime ideal B ofR is the direct sum of copies ofE(R/B) for prime ideals D ⊃ B, and if B is maximal, the injective cover is a finite sum of copies ofE(R/B). For a finitely generatedR-moduleM withn generators andG an injectiveR-module, we argue that the natural mapG ⁿ →G ⁿ/Hom _R (M, G) is an injective precover if Ext _R ¹ (M, R) = 0, and that the converse holds ifG is an injective cogenerator ofR. Consequently, for a maximal ideal R ofR, depth_R R ≧ 2 if and only if the natural mapE(R/R) →E(R/R)/R/R is an injective cover and depth_R R > 0.     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

Isomorphisms ofp-adic group rings

SupposeP is the ring ofp-adic integers,G is a finite group of orderp ⁿ , andPG is the group ring ofG overP. IfV _p (G) denotes the elements ofPG with coefficient sum one which are of order a power ofp, it is shown that the elements of any subgroupH ofV _p (G) are linearly independent overP, and if in additionH is of orderp ⁿ , thenPGPH. As a consequence, the lattice of normal subgroups ofG and the abelianization of the normal subgroups ofG are determined byPG.     

The fitting length of solvableH pn-groups

For a (finite) groupG and some prime powerp ⁿ, theH _p ⁿ -subgroupH _pn (G) is defined byH _p ⁿ (G)=〈xεG|x ^pn≠1〉. A groupH≠1 is called aH _p ⁿ -group, if there is a finite groupG such thatH is isomorphic toH _p ⁿ (G) andH _p ⁿ (G)≠G. It is known that the Fitting length of a solvableH _p ⁿ -group cannot be arbitrarily large: Hartley and Rae proved in 1973 that it is bounded by some quadratic function ofn. In the following paper, we show that it is even bounded by some linear function ofn. In view of known examples of solvableH _p ⁿ -groups having Fitting lengthn, this result is “almost” best possible.     

Bounds of eigenvalues of a graph

LetG be a simple graph withn vertices. We denote by _i(G) thei-th largest eigenvalue ofG. In this paper, several results are presented concerning bounds on the eigenvalues ofG. In particular, it is shown that –1₂(G)(n–2)/2, and the left hand equality holds if and only ifG is a complete graph with at least two vertices; the right hand equality holds if and only ifn is even andG2K _n/2.     

Isoperimetric inequalities in potential theory

Given a non-empty bounded domainG in ⁿ ,n2, letr ₀(G) denote the radius of the ballG ₀ having center 0 and the same volume asG. The exterior deficiencyd _e (G) is defined byd _e (G)=r _e (G)/r ₀(G)–1 wherer _e (G) denotes the circumradius ofG. Similarlyd _i (G)=1–r _i (G)/r ₀(G) wherer _i (G) is the inradius ofG. Various isoperimetric inequalities for the capacity and the first eigenvalue ofG are shown. The main results are of the form CapG(1+cf(d _e (G)))CapG ₀ and ₁(G)(1+cf(d _i (G)))₁(G ₀),f(t)=t ³ ifn=2,f(t)=t ³/(ln 1/t) ifn=3,f(t)=t ^(n+3)/2 ifn4 (for convex G and small deficiencies ifn3).     

Limit distributions of expanding translates of certain orbits on homogeneous spaces

LetL be a Lie group and λ a lattice inL. SupposeG is a non-compact simple Lie group realized as a Lie subgroup ofL and . LetaεG be such that Ada is semisimple and not contained in a compact subgroup of Aut(Lie(G)). Consider the expanding horospherical subgroup ofG associated toa defined as U⁺ ={g&#x03B5;G:a ⁻ⁿ gaⁿ} →e as n → ∞. Let Ω be a non-empty open subset ofU ⁺ andn _i → ∞ be any sequence. It is showed that . A stronger measure theoretic formulation of this result is also obtained. Among other applications of the above result, we describeG-equivariant topological factors of L/gl × G/P, where the real rank ofG is greater than 1,P is a parabolic subgroup ofG andG acts diagonally. We also describe equivariant topological factors of unipotent flows on finite volume homogeneous spaces of Lie groups.     

The algebra ofG-relations

In this paper, we study a tower {A _n ^G: n} ≥ 1 of finite-dimensional algebras; here, G represents an arbitrary finite group,d denotes a complex parameter, and the algebraA _n ^G(d) has a basis indexed by ‘G-stable equivalence relations’ on a set whereG acts freely and has 2n orbits. We show that the algebraA _n ^G(d) is semi-simple for all but a finite set of values ofd, and determine the representation theory (or, equivalently, the decomposition into simple summands) of this algebra in the ‘generic case’. Finally we determine the Bratteli diagram of the tower {A _n ^G(d): n} ≥ 1 (in the generic case).     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

More results on Ramsey—Turán type problems

The paper deals with common generalizations of classical results of Ramsey and Turán. The following is one of the main results. Assumek≧2, ε>0,G _n is a sequence of graphs ofn-vertices and at least 1/2((3k?5) / (3k?2)+ε)n ² edges, and the size of the largest independent set inG _n iso(n). LetH be any graph of arboricity at mostk. Then there exists ann ₀ such that allG _n withn>n ₀ contain a copy ofH. This result is best possible in caseH=K _2k .     

Lower degree bounds for modular invariants and a question of I. Hughes

We prove two statements. The first one is a conjecture of Ian Hughes which states that iff ₁, ..., f_n are primary invariants of a finite linear groupG, then the least common multiple of the degrees of thef _i is a multiple of the exponent ofG.The second statement is about vector invariants: IfG is a permutation group andK a field of positive characteristicp such thatp divides |G|, then the invariant ringK[V ^m]^G ofm copies of the permutation moduleV overK requires a generator of degreem(p–1). This improves a bound given by Richman [6], and implies that there exists no degree bound for the invariants ofG that is independent of the representation.     

Graphs isomorphic to subgraphs of their iterated line graphs

A graphG is said to be embeddable into a graphH, if there is an isomorphism ofG into a subgraph ofH. It is shown in this paper that every unicycle or tree which is neither a path norK _1,3 embeds in itsn-th iterated line graph forn1 or 2, 3, and that every other connected graph that embeds in itsn-th iterated line graph may be constructed from such an embedded unicycle or tree in a natural way. A special kind of embedding of graph into itsn-th iterated line graph, called incidence embedding, is studied. Moreover, it is shown that for every positive integerk, there exists a graphG such that (G) = , where (G) is the leastn1 for whichG embeds inL ⁿ(G).     

Decomposable graphs and definitions with no quantifier alternation

Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D₀(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q₀(n) to be the minimum of D₀(G) over all graphs G of order n.We prove that for all n we have

log^*n−log^*log^*n−2≤q₀(n)≤log^*n+22,