Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

Linear upper bounds for local Ramsey numbers

A coloring of the edges of a graph is called alocal k-coloring if every vertex is incident to edges of at mostk distinct colors. For a given graphG, thelocal Ramsey number, r _loc ^k (G), is the smallest integern such that any localk-coloring ofK _n , (the complete graph onn vertices), contains a monochromatic copy ofG. The following conjecture of Gyárfás et al. is proved here: for each positive integerk there exists a constantc = c(k) such thatr _loc ^k (G) cr ^k (G), for every connected grraphG (wherer ^k (G) is theusual Ramsey number fork colors). Possible generalizations for hypergraphs are considered.On leave from the Institute of Mathematics, Technical University of Warsaw, Poland.While on leave at University of Louisville, Fall 1985.     

In the square of graphs,hamiltonicity and pancyclicity,Hamiltonian connectedness and panconnectedness are equivalent concepts

The squareG ² of a graphG has the same point set asG, and two points ofG ² are adjacent inG ² if and only if their distance inG is at most two. The result thatG ² is Hamiltonian ifG is two-connected, has been established early in 1971. A conjecture (ofA. Bondy) followed immediately: SupposeG ² to have a Hamiltonian cycle; is it true that for anyvV(G), there exist cyclesC _j containingv and having arbitrary lengthj, 3j|V(G)|. The proof of this conjecture is one of the two main results of this paper. The other main result states that ifG ² contains a Hamiltonian pathP(v, w) joining the pointsv andw, thenG ² contains for anyj withd _G ² (v, w)j|V(G)|–1 a pathP _j (v, w) of lengthj joiningv andw. By this, a conjecture ofF. J. Faudree andR. H. Schelp is proved and generalized for the square of graphs.However, to prove these two results extensive preliminary work is necessary in order to make the proof of the main results transparent (Theorem 1 through 5); and Theorem 3 plays a central role for the main results. As can be seen from the statement of Theorem 3, the following known results follow in a stronger form: (a) IfG is two-connected, thenG ² is Hamiltonian-connected; (b) IfG is two-connected, thenG ² is 1-Hamiltonian.Dedicated to Prof. Dr. E. Hlawka on the occasion of his 60th birthday     

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.     

Mortality of iterated Gallai graphs

For a finite or infinite graphG, theGallai graph (G) ofG is defined as the graph whose vertex set is the edge setE(G) ofG; two distinct edges ofG are adjacent in (G) if they are incident but do not span a triangle inG. For any positive integert, thetth iterated Gallai graph ^t (G) ofG is defined by ( ^t–1(G)), where ⁰(G):=G. A graph is said to beGallai-mortal if some of its iterated Gallai graphs finally equals the empty graph. In this paper we characterize Gallai-mortal graphs in several ways.     

Building ofGL(m, D) and centralizers

LetG=GL(m, D) whereD is a central division algebra over a commutative nonarchimedean local fieldF. LetE/F be a field extension contained inM(m, D). We denote byI (resp.I _E) the nonextended affine building ofG (resp. of the centralizer ofE ^x inG). In this paper we prove that there exists a uniqueG _E-equivariant affine mapj _EI_EI. It is injective and its image coincides with the set ofE ^x-fixed points inI. Moreover, we prove thatj _E is compatible with the Moy-Prasad filtrations.This author's contribution was written while he was a post-doctoral student at King's College London and supported by an european TMR grant     

Partitions of bi-partite numbers into at mostj parts

The number of partitions of a bi-partite number into at mostj parts is studied. We consider this function,p _j (x, y), on the linex+y=2n. Forj4, we show that this function is maximized whenx=y. Forj>4 we provide an explicit formula forn _j so that, for allnn _j ,x=y yields a maximum forp _j (x,y).     

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.     

On the asymptotic and invariantσ-algebras of random walks on locally compact groups

Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , ^a ,Q) andL (G , ⁱ ,Q) where ^a and ⁱ stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , ^a ,Q) L (G , ⁱ ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers ⁿ.     

Farrell cohomology and Brown theorems for profinite groups

LetG be a profinite group which has an open subgroupH such that the cohomologicalp-dimensiond≔cd_p(H) is finite (p is a fixed prime). The main result of this paper expresses thep-primary part of high degree cohomology ofG in terms of the elementary abelianp-subgroups ofG: From the latter one constructs a natural profinite simplicial setA G, on whichG acts by conjugation. ThenH ⁿ(G,M)≅H _G ⁿ (AG,M) holds forn≧d+r and everyp-primary discreteG-moduleM (r≔p-rank ofG). If one uses profinite Farrell cohomology, which is introduced in this paper, the analogous fact holds in all degrees. These results are the profinite analogues of theorems by K.S. Brown for discrete groups.     

Decomposition of bipartite multigraphs into matchings

Summary In this paper we show that a bipartite multigraphG in which no vertex is adjacent to more thann edges may be decomposed into any numbern ^*n of matchings in such a way that the number of edges in each of these matchings differ from one another by at most one unit. When the two sets of verticesX and¯X ofG are partitioned into subsetsX _i and¯X _j respectively, we give conditions for the existence of a decomposition ofG inton ^*n matchings such that each matching contains at most _i edges adjacent to vertices inX _i and at most _j edges adjacent to vertices in¯X _j .There are many practical problems of scheduling with resource limitations for which such decompositions of a bipartite graph are required; some examples are given.

---

Zusammenfassung Es wird gezeigt, daß ein bipartiter MultigraphG, in dem in keinem Knoten mehr alsn Kanten zusammenstoßen, in eine beliebige Zahln ^*n von matchings dekomponiert werden kann, und zwar derart, daß die Zahl der Kanten in jedem dieser matchings untereinander um höchstens eins differiert. Mit dem Aufteilen der beiden KnotenmengenX und ¯X vonG in UntermengenX _i und¯X _j werden Bedingungen für die Existenz einer Dekomposition vonG inn ^* n matchings angegeben, wobei jedes matching höchstens _i ( _j ) Kanten enthält, die in den KnotenX _i (bzw.¯X _j ) zusammenstoßen.Es gibt viele praktische Planungsprobleme mit beschränkten Ressourcen, für die solche Dekompositionen von bipartiten Graphen verlangt werden; einige Beispiele werden angeführt.

---

---

This work was supported by a grant from the National Research Council of Canada.     

Quasinormalität in topologischen Gruppen

LetQ be a subgroup of the locally compact groupG. Q is called a topologically quasinormal subgroup ofG, ifQ is closed and for each closed subgroupA ofG. We prove: If the compact elements ofG form a proper subgroup, compact topologically quasinormal subgroups ofG are subnormal of defect 2. IfG is connected, compact topologically quasinormal subgroups ofG are normal. IfG/G ₀ is compact, connected topologically quasinormal subgroups ofG are normal.     

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.     

On finite groups whose every proper normal subgroup is a union of a given number of conjugacy classes

Let G be a finite group andA be a normal subgroup ofG. We denote by ncc(A) the number ofG-conjugacy classes ofA andA is calledn-decomposable, if ncc(A)= n. SetK _G = {ncc(A)|A ⊲ G}. LetX be a non-empty subset of positive integers. A groupG is calledX-decomposable, ifK _G =X. Ashrafi and his co-authors [1-5] have characterized theX-decomposable non-perfect finite groups forX = {1, n} andn ≤ 10. In this paper, we continue this problem and investigate the structure ofX-decomposable non-perfect finite groups, forX = {1, 2, 3}. We prove that such a group is isomorphic to Z₆, D₈, Q₈, S₄, SmallGroup(20, 3), SmallGroup(24, 3), where SmallGroup(m, n) denotes the mth group of ordern in the small group library of GAP [11].     

The minimum diameter of orientations of complete multipartite graphs

Given a graphG, letB be the family of strong orientations ofG, and define A pair {p,q} of integers is called aco-pair if 1 p q . A multiset {p, q, r} of positive integers is called aco-triple if {p, q} and {p, r} are co-pairs. LetK(p₁, p₂,..., p_n) denote the completen-partite graph havingp _i vertices in theith partite set.In this paper, we show that if {p ₁, p₂,...,p_n} can be partitioned into co-pairs whenn is even, and into co-pairs and a co-triple whenn is odd, then(K(p₁, p₂,..., p_n)) = 2 provided that (n,p ₁, p₂, p₃, p₄) (4, 1, 1, 1, 1). This substantially extends a result of Gutin [3] and a result of Koh and Tan [4].     

The birth and death processes with zero as their absorbing barrier

LetE=(0, 1,...), Q ^b=(q_ij), i, j=0, 1, ..., whereq _{i, i–1}=a_i, q_{i, i+1}=b_i, q_ii=–(a_i+b_i), q_ij=0, when|i–j|>1. a ₀=0, b₀=b>0, a_i, b_i>0 (i>0). Lettingb=0 inQ ^b, we get the matrixQ ⁰.The time homogeneous Markov processX ^b ={x ^b (t,w), 0t< ^b (w)} (X ⁰={x⁰(t,w), 0t<⁰(w)}), withQ ^b (Q ⁰, respectively) as its density matrix and withE as its state space, is calledQ ^b (Q ⁰, respectively) process in this paper.Q ^b andQ ⁰ processes are all called the birth and death processes, with zero being the reflecting barrier ofQ ^b processes, the absorbing barrier ofQ ⁰ processes.AllQ ^b processes have been constructed by both probability and analytical methods (Wang [2], Yang [1]). In this paper, theQ ⁰ processes are imbedded intoQ ^b processes and all theQ ⁰ processes are directly constructed from theQ ^b processes. The main results are:Letb>0 be arbitrarily fixed, then there is a one to one correspondence between theQ ⁰ processes and theQ ^b processes (in the sense of transition probability).TheQ ⁰ process is unique iffR ^*=. SupposingR<, then:IfX ⁰={x⁰(t,w), 0t<⁰(w)} is a non-minimalQ ⁰ process, then its eigensequence (p, q, r _n, n–1) satisfies § 4(7).Conversely, let a non-negative number sequence (p, q, r _n, n–1) satisfying § 4(7) be arbitrarily given, then there exists a unique non-minimalQ ⁰ processX ⁰ with eigensequence (p, q, r _n, n–1). The Laplace transform of the transition probability (p _ij ⁰ (t)) ofX ⁰ is determined by § 4(15). X ⁰ is honest iffr _–1=0.X ⁰ satisfies the forward equation iffp=0.     

Topologisch quasinormale Untergruppen zusammenhängender lokalkompakter Gruppen

A closed subgroupQ of a topological groupG is called topologically quasinormal (tqn) inG if holds for every closed subgroupA ofG. We show that every tqn subgroup of a connected locally compact group is actually a normal subgroup. Besides we prove: a homogeneous spaceG/H of a connected Lie groupG with the property that every non-trivial one-parameter orbit is dense has dimension at most one.     

On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.