On a connection between the existence ofk-trees and the toughness of a graph

A graphG has toughnesst(G) ift(G) is the largest numbert such that for any subsetS of the vertices ofG, the number of vertices inS is at leastt times the number of components ofG on deletion of the vertices inS, provided that there is then more than one component. Ak-tree of a connected graph is a spanning tree with maximum degree at mostk. We show here that if , withk 3, thenG has ak-tree. The notion of ak-tree generalizes the casek = 2 of a hamiltonian path, so that this result, as we discuss, may be of some interest in connection with Chvátal's conjecture that, for somet, every graph with toughness at leastt is hamiltonian.     

Compactification of symmetric varieties

The symmetric varieties considered in this paper are the quotientsG/H, whereG is an adjoint semi-simple group over a fieldk of characteristic 2, andH is the fixed point group of an involutorial automorphism ofG which is defined overk. In the casek=C, De Concini and Procesi (1983) constructed a wonderful compactification ofG/H. We prove the existence of such a compactification for arbitraryk. We also prove cohomology vanishing results for line bundles on the compactification. Dedicated to the memory of C. Chevalley     

Power automorphisms of finitep-groups

For a finite groupG letA(G) denote the group of power automorphisms, i.e. automorphisms normalizing every subgroup ofG. IfG is ap-group of class at mostp, the structure ofA (G) is shown to be rather restricted, generalizing a result of Cooper ([2]). The existence of nontrivial power automorphisms, however, seems to impose restrictions on thep-groupG itself. It is proved that the nilpotence class of a metabelianp-group of exponentp ² possessing a nontrival power automorphism is bounded by a function ofp. The “nicer” the automorphism—the lower the bound for the class. Therefore a “type” for power automorphisms is introduced. Several examples ofp-groups having large power automorphism groups are given.     

Additive Latin transversals and group rings

LetA={a ₁, …,a _k} and {b ₁, …,b _k} be two subsets of an abelian groupG, k≤|G|. Snevily conjectured that, when |G| is odd, there is a numbering of the elements ofB such thata _i+b _i,1≤i≤k are pairwise distinct. By using a polynomial method, Alon affirmed this conjecture for |G| prime, even whenA is a sequence ofk<|G| elements. With a new application of the polynomial method, Dasgupta, Károlyi, Serra and Szegedy extended Alon’s result to the groupsZ _p ^r andZ _p ^rin the casek<p and verified Snevily’s conjecture for every cyclic group. In this paper, by employing group rings as a tool, we prove that Alon’s result is true for any finite abelianp-group withk<√2p, and verify Snevily’s conjecture for every abelian group of odd order in the casek<√p, wherep is the smallest prime divisor of |G|. This work has been supported partly by NSFC grant number 19971058 and 10271080.     

Distinguished extensions of a lattice-ordered group

Any lattice-ordered group (l-group for short) is essentially extended by its lexicographic product with a totally ordered group. That is, anl-homomorphism (i.e., a group and lattice homomorphism) on the extension which is injective on thel-group must be injective on the extension as well. Thus nol-group has a maximal essential extension in the categoryIGp ofl-groups withl-homomorphisms. However, anl-group is a distributive lattice, and so has a maximal essential extension in the categoryD of distributive lattices with lattice homomorphisms. Adistinguished extension of onel-group by another is one which is essential inD. We characterize such extensions, and show that everyl-groupG has a maximal distinguished extensionE(G) which is unique up to anl-isomorphism overG.E(G) contains most other known completions in whichG is order dense, and has mostl-group completeness properties as a result. Finally, we show that ifG is projectable then E(G) is the -completion of the projectable hull ofG.Presented by M. Henriksen.     

Zwei Klassen lokalkompakter maximal fastperiodischer Gruppen

In this paper we study the class of all locally compact groupsG with the property that for each closed subgroupH ofG there exists a pair of homomorphisms into a compact group withH as coincidence set, and the class of all locally compact groupG with the property that finite dimensional unitary representations of subgroups ofG can be extended to finite dimensional representations ofG. It is shown that [MOORE]-groups (every irreducible unitary representation is finite dimensional) have these two properties. A solvable group in is a [MOORE]-group. Moreover, we prove a structure theorem for Lie groups in the class [MOORE], and show that compactly generated Lie groups in [MOORE] have faithful finite dimensional unitary representations.     

Independent sets,cliques and hamiltonian graphs

LetG be ak-connected (k 2) graph onn vertices. LetS be an independent set ofG. S is called essential if there exist two distinct vertices inS which have a common neighbor inG. LetV _r, be a clique which is a complete subgraph ofG. In this paper it is proven that if every essential independent setS ofk + 1 vertices satisfiesS V _r , thenG is hamiltonian, orG{u} is hamiltonian for someu V _r, orG is one of three classes of exceptional graphs. Our theorem generalizes several well-known theorems.     

A mixed version of Menger's theorem

An(a, b)-n-fan means a union ofn internally disjoint paths. Menger's theorem states that a graphG has an(a, b)-n-fan if and only ifG isn-connected betweena andb. We show thatG contains edge-disjoint(a, b)-n-fans if and only if for anyk withk0min{n–1, |V(G)|–2} and for any subsetX ofV(G)-{a, b} with cardinalityk, G-X is (n-k)-edge-connected betweena andb.     

Some conditions which almost characterize Frobenius groups

The main result of this paper is the following: LetG be a group with a proper non-trivial normal subgroupH such that each coset ofH distinct fromH is contained in a conjugacy class ofG. IfG is not a Frobenius group with kernelH then one ofH orG/H is ap-group. The hypothesis of this theorem is shown to be equivalent to a condition on characters ofG. The only group the author knows which satisfies this hypothesis and is not either Frobenius or ap-group is one of order 72.     

On pro-p-groups with a single defining relator

We find necessary and sufficient conditions for the factor groups of the derived series of a pro-p-group with a single defining relation to be torsion free. For such groupsG we prove that the group algebra ℤ _pG is a domain and the cohomological dimension ofG is at most 2.     

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.     

The structure of a collineation group preserving an oval in a projective plane of odd order

We investigate the structure of a collineation groupG preserving an oval in a finite projective plane of odd order and we obtain several results aboutG, whenG is a2-group. These results are then used to investigate the structure ofG/O(G) in the general case and, in particular, that ofF*(G/O(G)).This research was supported in part by a grant from the M.U.R.S.T.     

Toughness and the existence ofk-factors. II

In a paper with the same title [3], we proved Chvátal's conjecture thatk-tough graphs havek-factors if they satisfy trivial necessary conditions. In this paper, we prove the following stronger result: Suppose|V(G)| k + 1,k |V(G)| even, and|S| k w(G – S) – 7/8k ifw(G – S) 2, wherew(G – S) is the number of connected components ofG – S. ThenG has ak-factor.     

The most vital edges with respect to the number of spanning trees in two-terminal series-parallel graphs

A setE ofk edges in a multigraphG=(V,E) is said to be ak most vital edge set (k-MVE set) if these edges being removed fromG, the resultant graphG=(V,E –E) has minimum number of spanning trees. The problem of finding ak-MVE set for two-terminal series-parallel graphs is considered in this paper. We present anO (|E|) time algorithm for the casek=1, and anO(|V| ^k +|E|) time algorithm for arbitraryk.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

W v cycles in plane graphs

A cycle in a plane graphG is called aW _v cycle if it has a connected (or empty) intersection with each face of the graph. We show that if the minimum degree (G)3 thenG has aW _v cycle and the lengthw(G) of a longestW _v cycle is bounded by the number,f(G), of faces ofG. The classW of graphsG withw(G)=f(G) is completely characterized by an characterized by an inductive construction from two graphs, namelyK ₄ and a face merging of two copies ofK ₄ on one hand, and in terms involving Halin graphs and face merging on the other hand. Longest cycles in members ofW are investigated. The shortness coefficient ofW is proved to be between one-half and three-quarters inclusively.     

Sur l'équivalence de certaines mesures produit

Sommaire SoitG={g _k ,kN} une suite de variables aléatoires gaussiennes centrées réduites et indépendantes; soit de plusY={y _k ,kN} une suite indépendante deG de variables aléatoires indépendantes. On étudie à quelles conditions la loi deG+Y est équivalente à celle deG. On utilise pour cela les lois zéro-un vérifiées parG en analysant leurs effets, maximaux sur la loi deY.

---

Summary LetG={g _k ,kN} be a sequence of independent Gaussian centred reduced random variables; let moreoverY={y _k ,kN} be a sequence independent ofG of independent random variables: For obtaining conditions characterizing the equivalence of the distributions ofG andG+Y, we use the zero-one laws verified byG, first for the convergence of the series _k g _k or _k (g _k ² –a _k ), secundly for the asymptotic behavior of the sequence {g _k ,kN} and we analyze their maximal effects on the distribution ofY.

     

On existence of finite universal Korovkin sets in the centre of group algebras

In this paper, we characterize compact groupsG as well as connected central topological groupsG for which the centreZ(L ¹(G)) admits a finite universal Korovkin set. Also we prove that ifG is a non-connected central topological group which has a compact open normal subgroupK such thatG=KZ, thenZ(L ¹(G)) admits a finite universal Korovkin set if is a finite-dimensional separable metric space or equivalentlyG is separable metrizable andG/K has finite torsion-free rank.     

Contractible edges in non-separating cycles

An edge of ak-connected graph is said to bek-contractible if the contraction of the edge results in ak-connected graph. We prove that every triangle-freek-connected graphG has an induced cycleC such that all edges ofC arek-contractible and such thatG–V(C) is (k–3)-connected (k4). This result unifies two theorems by Thomassen [5] and Egawa et. al. [3].Dedicated to Professor Toshiro Tsuzuku on his sixtieth birthday