For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

On computing the number of subgroups of a finite Abelian group

We consider the numberN _A (r) of subgroups of orderp ^r ofA, whereA is a finite Abelianp-group of type =₁,₂,..., _l ()), i.e. the direct sum of cyclic groups of order ⁱⁱ. Formulas for computingN _A (r) are well known. Here we derive a recurrence relation forN _A (r), which enables us to prove a conjecture of P. E. Dyubyuk about congruences betweenN _A (r) and the Gaussian binomial coefficient .     

Singular perturbations in foliations

Summary We define a constraint system , [0,₀), which is a kind of family of vector fields on a manifold. This is a generalized version of the family of the equations , [0,₀),x ^m ,y ⁿ . Finally, we prove a singular perturbation theorem for the system , [0,₀).Dedicated to Professor Kenichi Shiraiwa on his 60th birthday     

SU2ℍ als Kollineationsgruppe von sechzehndimensionalen lokalkompakten Translationsebenen

As a contribution to a classification of all sixteen-dimensional translation planes whose collineation group has dimension at least 38, this paper deals with the case that contains a subgroup (locally) isomorphic to SU₂Spin₅. Under various further assumptions, it is shown that such a plane satisfying dim 38 is necessarily isomorphic to the classical plane over the octonions.The complete classification will reveal that these further assumptions may in fact be omitted, except for the case that even contains a subgroup isomorphic to Spin₇. The latter planes have been explicitly determined in previous papers.

Meinem verehrten Lehrer Helmut Salzmann zum 65. Geburtstag     

The completions of a commutative lattice group with respect to the intrinsic topologies

In this paper we discuss the completions (, ) of a commutativel-groupG with respect to the intrinsic topologies . We give some conditions under which is the intrinsic topology of the same type on as and give the relations between these completions.     

Théorème de division avec des conditions au bord

Let be an open subset of ⁿ and be a subalgebra of the algebra of analytic functions on . We suppose that satisfies some weak conditions of noetherianity such that we can construct a finite stratification for each ideal of . We also suppose that satifies global £ojasiewicz's inequalities. We prove the following: Let andf C on flat on ; if for eacha the Taylor's serie off ata, T _a f, is in the ideal generated byT _a f ₁,...,T _a f _p in the ring of formal power series, then there exist ₁,..., _p ,C on flat on such that . This result extends the classic Hormander's theorem of division (for a polynomial) or the £ojasiewicz-Malgrange theorem in the local analytic case.Reherches menées dans le cadre du Programme d'Appui à la Recherche Scientifique (PARS MI 33)     

Boundedness in the mean of orthonormalized polynomials

For the polynomials {p_n(t)} ₀ , orthonormalized on [–1, 1] with weightp(t) = (1–t) (1+t) _v=1 ^m , we obtain necessary and sufficient conditions for boundedness of the sequences of norms: 1) 2) and 3) with the conditions that on [–1, 1] and (H,)^–1 L²(0, 2), where(H,) is the modulus of continuity in C(–1, 1) of function H.Translated from Matematicheskie Zametki, Vol. 13, No. 5, pp. 759–770, May, 1973.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

On the stochastic independence properties of hard-core distributions

A probability measurep on the set of matchings in a graph (or, more generally 2-bounded hypergraph) ishard-core if for some : [0,), the probabilityp(M) ofM is proportional to . We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, withM chosen according to the hard-core distributionp, MP () the matching polytope of , and >0, if the vector ofmarginals, (Pr(AM):A an edge of ), is in (1–) MP (), then the weights (A) are bounded by someA(). This eventually implies, for example, that under the same assumption, with fixed, as the distance betweenA, B tends to infinity.Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]–[13]).Supported in part by NSFThis work forms part of the author's doctoral dissertation [16]; see also [17]. The author gratefully acknowledges NSERC for partial support in the form of a 1967 Science and Engineering Scholarship.     

Summierbarkeit der geometrischen Reihe auf vorgeschriebenen Mengen

In this paper we are concerned with the summability of the geometric series by matrix methods. We prove the following theorem: Suppose M_o:={z:|z|<1}, M₁, M₂, is a collection of countably many Lebesgue measureable, disjoint sets. For k=1,2, let f_k be a prescribed function, analytic on . Then there exists a triangular matrix , such that the V-transform {_n(z)} of the geometric series has the following properties: {_n(z)} converges compactly to on M_o; for k=1,2, there are sets B_k, such that has Lebesgue-measure zero and _n(z)f_k(z) for zB_k; if there is a set B^*, such that B^*M^* has Lebesgue-measure zero and {_n(z)} diverges for zB^*.     

Exceptional Sequences in Hall Algebras and Quantum Groups

Let be a finite-dimensional hereditary algebra over a finite field k, () and () be, respectively, the Hall algebra and the composition algebra of , be the isomorphism classes of finite dimensional -modules and I the isomorphism classes of simple -modules. We define and , in , to be the right and left derivations of () respectively. By using these derivations and the action of the braid group on the set of exceptional sequences of -mod, we provide an effective algorithm of calculating the root vectors of real Schur roots. This means that we get an inductive method to express u as the combinations of elements u_i in the Hall algebra, where i I and in is any exceptional -module. Because of the canonical isomorphism between the Drinfeld–Jimbo quantum group and the generic composition algebra, our algorithm is applicable directly to quantum groups. In particular, all the root vectors are obtained in this way in the finite type cases.     

Asymptotics for thenth-degree Laguerre polynomial evaluated atn

Summary We investigate the asymptotic behaviour of _n (n),n where _n (x) denotes the Laguerre polynomial of degreen. Our results give a partial answer to the conjecture _n (n)>1 forn>6, made in 1984 by van Iseghem. We also show the connection between this conjecture and the continued fraction approximants of .Work sponsored by the Consiglio Nazionale delle Ricerche and by the Ministero dell'Università e della Ricerca Scientifica e Tecnologica of Italy     

Sets with a Prescribed Number of Power Invariants

Let A₁,...,A_n be points in , let be a fixed point, let p be a positive integer, and let ₁,...,_n be positive real numbers. If the does not depend on the position of M on a sphere with center O, then one says that the point system {A₁,...,A_n} has an invariant of degree p with weight system {,...,_n}. It is proved that for arbitrary positive integers d and N there exists a finite point system having invariants of degrees p=1,...,N with common positive weight system {₁,...,_n}. Bibliography: 2 titles.     

Invariance principles for random walks on hypergroups on ℝ2 and ℕ

Let (X _n:n) be i.i.d. with finite variance and values in a hypergroupK:=₊ or and _j=1 ⁿ X _j be the randomized sum of these random variables. It is shown that the processes converge in distribution to a Gaussian process in the caseK=₊, that the processes converge towards a Bessel process on ₊ in the case of polynomial growth of the hypergroupK=₊ or , and that in the case of exponential growth converges towards a Brownian motion asn.     

Estimates for lebesgue constants in dimension two

Summary Let D denote the interior of a piecewise regular curve of R² having a point with Gauss curvature different from zero. We show that the Lebesgue constants L ^D relative to D behave like ^1/2 as .     

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 the Structure of a Certain Class of Mixed Tsirelson Spaces

We study Banach spaces of the form We call such a space a p-space, p[1,), if for every k the space is isomorphic to _pk and the sequence (p_k) strictly decreases to p. We examine the finite block representability of the spaces _r in a p-space proving that it depends not only on p but also on the sequences (p_k) and (n_k). Assuming that _i n_i ^1/q decreases to 0, where q is the conjugate exponent of p, we prove the existence of an asymptotic biorthogonal system in X and also that c ₀ is finitely representable in X. Moreover we investigate the modified versions of p-spaces proving that, if n_km1/pkm-1/pk_m-1 increases to infinity for a subsequence (n_km) , then ₁ embeds into X. We also investigate complemented minimality for the class of spaces where is either a subsequence of the sequence of Schreier classes ( _n)_{n N} or a subsequence of ( _n)_{n N}.     

Fonctions Séparément Finement Surharmoniques

Nous montrons que toute fonction séparément finement surharmonique sur un ouvert de la topologie produit _{n_1}×s× _{n_k} des topologies fines des espaces R ⁿ ₁,. . ., R ⁿ _k, _{n_1}×s× _{n_k}-localement bornée inférieurement est finement surharmonique dans . On en déduit que toute fonction séparément finement harmonique, _{n_1}×s× _{n_k}-localement bornée sur est finement harmonique dans .Separately Finely Superharmonic Functions Abstract.We prove that every separately finely surperharmonic function on an open set in R ⁿ ₁×s×R ⁿ _k for the product _{n_1}×s× _{n_k} of the fine topologies on the spaces R ⁿ ₁,. . ., R ⁿ _k, _{n_1}×s× _n-_klocally lower bounded, is finely superharmonic in . We then deduce that every separateltly finely harmonic function _{n_1}×s× _{n k}-locally bounded in is finely harmonic.     

On ηα-groups and fields

Let :=. The following are known: two -sets of power are isomorphic. Let >0. Two ordered divisible Abelian groups that are -sets of power are isomorphic, two real closed fields that are -sets of power are isomorphic. The following is shown: (1) there exist 2 nonisomorphic ordered Abelian groups (respectively ordered fields) that are -sets of power ; (2) there exist 2 nonisomorphic ordered divisible Abelian groups (respectively real closed fields) of power all having the same order type; (3) there exist 2 nonisomorphic ordered divisible Abelian groups (respectively real closed fields) that are -sets having the same order type.     

λ-Divergence of the Fourier Series of Continuous Functions of Several Variables

In this paper, we consider the behavior of rectangular partial sums of the Fourier series of continuous functions of several variables with respect to the trigonometric system. The Fourier series is called -convergent if the limit of rectangular partial sums over all indices for which for all j and k exists. In the space of arbitrary even dimension 2m we construct an example of a continuous function with an estimate of the modulus of continuity such that its Fourier series is -divergent everywhere for any .