k-regular factors and semi-k-regular factors in bipartite graphs

LetG be a graph, andk1 an integer. LetU be a subset ofV(G), and letF be a spanning subgraph ofG such that deg _F (x)=k for allx V(G)–U. If deg _F (x)k for allxU, thenF is called an upper semi-k-regular factor with defect setU, and if deg _F (x)k for allxU, thenF is called a lower semi-k-regular factor with defect setU. Now letG=(X, Y;E(G)) be a bipartite graph with bipartition (X,Y) such that X=Yk+2. We prove the following two results.(1) Suppose that for each subsetU ₁X such that U ₁=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=max{k+1, X+1/2},G has an upper semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.(2) Suppose that for each subsetU ₁X such that U ₁=X–1/k+1,G has a lower semi-k-regular factor with defect setU ₁Y, and for each subsetU ₂Y such that U ₂=X–1/k+1,G has a lower semi-k-regular factor with defect setXU ₂. ThenG has ak-factor.     

Polynomially convex orbits of compact lie groups

LetV be a finite dimensional complex linear space and letG be a compact subgroup of GL(V). We prove that an orbitG, V, is polynomially convex if and only ifG is closed andG is the real form ofG . For every orbitG which is not polynomially convex we construct an analytic annulus or strip inG with the boundary inG. It is also proved that the group of holomorphic automorphisms ofG which commute withG acts transitively on the set of polynomially convexG-orbits. Further, an analog of the Kempf-Ness criterion is obtained and homogeneous spaces of compact Lie groups which admit only polynomially convex equivariant embeddings are characterized.Supported by Federal program Integratsiya, no. 586.Supported by INTAS grant 97/10170.     

On flag-transitive affine planes of orderq 3

Let be a translation plane of orderq ³,q an odd prime power, whose kern GF(q). Letl be the line at infinity of . LetG be a solvable collineation group of in the linear translation complement, which acts transitively onl , and letH be a maximal normal cyclic subgroup ofG. Then the restriction ofH onl acts semiregularly onl and {1, 2, 3, 6}, where is the restriction ofG onl (ifq –1(mod 3), then {1, 2}). Ifq {3, 5} and {1, 2}, then is determined completely, using a computer.     

A Foliation of the Space of Conjugacy Classes of Representations of a Surface Group

Let be the fundamental group of a closed orientable surface of genus g 1, and let R(, G)/G be the space of conjugacy classes of representations of into a connected real reductive Lie group G. Motivated by the theory of geometric quantization, we define a map ¯ on R(, G)/G and investigate whether the fibres of ¯ are isotropic with respect to the natural symplectic structure on R(, G)/G. If g = 2 and G = SU(2), then the foliation given by the fibres of ¯ is equivalent to a real polarization defined by Weitsman, and we reprove his result that the fibres are isotropic in this case. If g = 1 then the fibres of ¯ are also isotropic, but we give an example to show that in general they are not.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Présentations des groupes de Fischer (II)

In this paper we give Coxeter presentation (X, ) for the three Fischer groupsG=Fi₂₂, Fi₂₃, Fi₂₄; we apply methods exposed in the first part. Each of these groups is generated by a class of 3-transpositions (named here a Fischer class) in which elements ofX are chosen. A subset of is the set of all the relations (xy) ^m(x,y)=1, wherex andy are inX and wherem(x,y) means the order ofxy inG. We obtainG as a specified quotient of the Coxeter group (X, ) with the appropriate diagram .     

Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. In this paper we give partial answers — affirmative and negative ones — to the general problem of determining if, for a function f mapping every end of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

Subsets with Restricted Movement

Let G be a finite permutation group on a set with no fixed points in and let m and k be integers with 0 < m < k. For a finite subset of the movement of is defined as move() = max_gG| ^g \ |. Suppose further that G is not a 2-group and that p is the least odd prime dividing |G| and move() m for all k-element subsets of . Then either || k + m or k (7m – 5) / 2, || (9m – 3)/2. Moreover when || > k + m, then move() m for every subset of .     

Covering the Hecke Triangle Surfaces

In the mid-1980s an equivalence was established between the simple closed geodesics on the Riemann surfaces obtained as quotients of the upper half plane H by any of the following subgroups of the modular group (1) : , (3), and ³. An axis of a hyperbolic element of (1) projects to a simple closed geodesic on one of these surfaces if and only if it does so on the other two.This equivalence was used to obtain a variety of Diophantine and geometric results. In subsequent related investigations, the role of (1) was assumed by the Hecke triangle group G_q for q 3. (For q = 3, we have (1) = G₃.) These works employed the analog of ³, denoted _q.In the context of the G_q, the present paper gives the analog of , which we denote _q. As in the case q = 3, we have [_q:_q] = 2. A rather full discussion of geometry of _q\ H is given. In particular, we demonstrate that the equivalence of simple closed geodesics on _q\ H and _q\ H does not hold for q 7.As of this writing, we have not been able to obtain an appropriate analog of (3).     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

On a Test Statistic for Linear Trend

Let {W(s)} _s 0 be a standard Wiener process. The supremum of the squared Euclidian norm Y (t)², of the R²-valued process Y(t)=(1/t W(t), {12/t ³ int_{0 t} s dW (s)– {3/t} W(t)), t [, 1], is the asymptotic, large sample distribution, of a test statistic for a change point detection problem, of appearance of linear trend. We determine the asymptotic behavior P {sup _t [, 1] Y(t)² > u as u , of this statistic, for a fixed (0,1), and for a moving = (u) 0 at a suitable rate as u . The statistical interest of our results lie in their use as approximate test levels.     

On the angular derivative and univalence

f . , , — , A f f(). , , f() 0 . , , ,A , f . , f() - f() . , , . (1976) ( ¦f(z)¦<1) . . (1969) ( ).     

Weight functions on the Kneser graph and the solution of an intersection problem of Sali

LetX, Y be finite sets and suppose thatF is a collection of pairs of sets (F, G),FX,GY satisfying |FF|s, |GG|t and |FF|+|GG|s+t+1 for all (F, G),F, GF. Extending a result of Sali, we determine the maximum ofF.     

Spanning trees with bounded degrees

Lets andk be positive integers. We prove that ifG is ak-connected graph containing no independent set withks+2 vertices thenG has a spanning tree with maximum degree at mosts+1. Moreover ifs3 and the independence number (G) is such that (G)1+k(s–1)+c for some0ck thenG has a spanning tree with no more thanc vertices of degrees+1.     

Dimension Theory and Nonstable K1 of Quadratic Modules

Employing Bak's dimension theory, we investigate the nonstable quadratic K-group K _1,2n (A, ) = G _2n (A, )/E _2n (A, ), n 3, where G _2n (A, ) denotes the general quadratic group of rank n over a form ring (A, ) and E _2n (A, ) its elementary subgroup. Considering form rings as a category with dimension in the sense of Bak, we obtain a dimension filtration G _2n (A, ) G _2n ⁰(A, ) ; G _2n ¹(A, ) ... E _2n (A, ) of the general quadratic group G _2n (A, ) such that G _2n (A, )/G _2n ⁰(A, ) is Abelian, G _2n ⁰(A, ) G _2n ¹(A, ) ... is a descending central series, and G _2n ^d(A)(A, ) = E _2n (A, ) whenever d(A) = (Bass–Serre dimension of A) is finite. In particular K _1,2n (A, ) is solvable when d(A) < .     

On the radicals of structural matrix rings

The relationship between the radical of a ringR and a structural matrix ring overR has been determined for some radicals. We continue these investigations, amongst others, determining exactly which radicals have the property (M(,R))=M( _s ,(R))+M( _a ,⁺(R))for any structural matrix ringM(,R) and finding (M(,R)) for any hereditary subidempotent radical .     

The size Ramsey number

Let denote the class of all graphsG which satisfyG(G ₁,G ₂). As a way of measuring minimality for members of, we define thesize Ramsey number (G ₁,G ₂) by.We then investigate various questions concerned with the asymptotic behaviour of.     

On π-Solvable and Locally π-Solvable Groups with Factorization

We prove that, in a locally -solvable group G = AB with locally normal subgroups A and B, there exist pairwise-permutable Sylow - and p-subgroups A , A _p and B , B _p , p , of the subgroups A and B, respectively, such that A B is a Sylow -subgroup of the group G and, for an arbitrary nonempty set ,

Some Ramsey-Turán type results for hypergraphs

To everyk-graphG let(G) be the minimal real number such that for every>0 andn>n ₀(,G) everyk-graphH withn vertices and more than (+) ( ) edges contains a copy ofG. The real number (G) is defined in the same way adding the constraint that all independent sets of vertices inH have sizeo(n). Answering a problem of Erds and Sós it is shown that there exist infinitely manyk-graphs with 0<(G)<(G) for everyk3. It is worth noting that we were unable to find a singleG with the above property.This paper was written while the authors were visiting AT&T Bell Laboratories, Murray Hill, NJ 07974.