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.     

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.     

Quelques resultats d'entropie sur l'espace de Wiener

One studies three problems related to entropy phenomenon in the classical Wiener space. In particular, the minoration of the Wiener measure for the set {xX/(x)} is given where is a Sobolev norm in the Wiener spaceX.

     

Brownian charges around loops

Summary Let (X _t ⁿ ) be a Poisson sequence of independent Brownian motions in ^d ,d3; Let be a compact oriented submanifold of d, of dimensiond–2 and volume ; let t be the sum of the windings of (X _s ⁿ , 0st) around ; then t/t converges in law towards a Cauchy variable of parameter /2. A similar result is valid when the winding is replaced by the integral of a harmonic 1-form in ^d .     

Weakly isomorphic transformations that are not isomorphic

Summary A new method for construction of transformations T _i: (X _i, B _i, _i) , i=1,2, that are factors of each other but that are not measuretheoretically isomorphic is provided. This method uses ergodic product cocycles of the form S ⁱ ₁xS ⁱ ₂x...,, where : XZ ₂ is a cocycle, S belongs to the centralizer of T and T is an ergodic translation on a compact, monothetic group X.     

Notes on Coalition Lattices

Given a finite partially ordered set P, for subsets or, in other words coalitions X, Y of P let X Y mean that there exists an injection : X Y such that x (x) for all x X. The set L(P) of all subsets of P equipped with this relation is a partially ordered set. When L(P) is a lattice, it is called the coalition lattice of P. It is shown that P is determined by the coalition lattice L(P). Further, any coalition lattice satisfies the Jordan–Hölder chain condition. The so-called winning coalitions, i.e. coalitions X such that P\X X in L(P), are shown to form a dual ideal in L(P). Finally, an inductive formula on P is given to describe the lattice operations in L(P), and this result also works for certain quasiordered sets P.     

Einschließungsaussagen für gewöhnliche Differentialoperatoren

Summary For differential operatorsM of second order (as defined in (1.1)) we describe a method to prove Range-Domain implications—Mu–u and an algorithm to construct these functions , , , . This method has been especially developed for application to non-inverse-positive differential operators. For example, for non-negativea ₂ and for given functions = we require =C ₀[0, 1] C ₂([0, 1]–T) whereT is some finite set), (M) (t)(t), (t[0, 1]–T) and certain additional conditions for eachtT. Such Range-Domain implications can be used to obtain a numerical error estimation for the solution of a boundary value problemMu=r; further, we use them to guarantee the existence of a solution of nonlinear boundary value problems between the bounds- and .     

An open mapping theorem for measures

LetX andY be Hausdorff spaces and denote byM (X) andM (Y) the corresponding spaces of finite and non-negative Borel measures, endowed with the weak topology. A Borel map :XY induces the map :M (X)M (Y). We give necessary and sufficient conditions for to be open. In case of being a surjection between Suslin spaces, is open if and only if is.     

L 2-approximation by the translates of a function and related attenuation factors

Summary Let be thek-dimensional subspace spanned by the translates (·–2j/k),j=0, 1, ...,k–1, of a continuous, piecewise smooth, complexvalued, 2-periodic function . For a given functionfL ²(–, ), its least squares approximantS _kf from can be expressed in terms of an orthonormal basis. Iff is continuous,S _kf can be computed via its discrete analogue by fast Fourier transform. The discrete least squares approximant is used to approximate Fourier coefficients, and this complements the works of Gautschi on attenuation factors. Examples of include the space of trigonometric polynomials where is the de la Valleé Poussin kernel, algebraic polynomial splines where is the periodic B-spline, and trigonometric polynomial splines where is the trigonometric B-spline.     

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.     

Theorem on a convergence condition in the spaces

For a given -function (u), a condition on a -function (u) is found such that it is necessary and sufficient for the following to hold: if f_n(x) f(x) and f _n (x)M (n=1, 2, ...) where M>0 is an absolute constant, then f _n (x)–f(x)0(n). An analogous condition for convergence in Orlicz spaces is obtained as a corollary.Translated from Matematicheskie Zametki, Vol. 21, No. 5, pp. 615–626, May, 1977.The author thanks V. A. Skvortsov for his constant attention and guidance on this paper.     

On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.     

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     

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.     

Regular homomorphisms of generalized projective planes

A generalized projective plane is an incidence structure together with a relation distant on the set of points and also on the set of lines, such that any two distant points A,B (lines a,b) have a unique common line (A,B) (common point (a,b)) and three further axioms hold. Every commutative ring with 1 supplies a model. A homomorphism of into an incidence structure is called regular if the following condition and its dual are valid: A distant B and c IA,B implies c=(A,B). We shall prove the following two theorems. Let be a generalized projective plane satisfying a richness condition called (U). Let M I m. If and are regular homomorphisms of such that X = M X = M for each point X of the line m then A = B A = B for any two points A,B. If is a projective plane over a commutative ring such that (U) holds then the surjective regular homomorphisms of are induced by the ideals of the ring; in particular, the image of under a regular homomorphism is again a projective plane over a ring, and preserves distant.     

Harmonic analysis on tori

We consider measurable subsets {ofR}ⁿ with 0<m()<, and we assume that has a spectral set . (In the special case when is also assumed open, may be obtained as the joint spectrum of a family of commuting self-adjoint operators {H _k: 1kn} in L ² () such that each H _k is an extension of i(/x _k) on C _c (), k=1, ..., n.)It is known that is a fundamental domain for a lattice if is itself a lattice. In this paper, we consider a class of examples where is not assumed to be a lattice. Instead is assumed to have a certain inhomogeneous form, and we prove a necessary and sufficient condition for to be a fundamental domain for some lattice in {ofR}ⁿ. We are thus able to decide the question, fundamental domain or not, by considering only properties of the spectrum . Our criterion is obtained as a corollary to a theorem concerning partitions of sets which have a spectrum of inhomogeneous form.Work supported in part by the NSF.Work supported in part by the NSRC, Denmark.     

Répartition de Suites et Équations Fonctionnelles Associées

LetX be a compact metric space, a probability measure onX, T a measure preserving transformation ofX into itself. Furthermore, letZ be a compact abelian group, andS the skew-product defined onX×Z by the formula:S(x,z)=(T x,z+(x)) where is some map fromX toZ. It is known that under the hypothesis of unique ergodicity for the triple (X, ,T) and some suitable conditions of continuity onT and , the triple (X×Z,m,S) wherem is the product measure of by the Haar measure onZ is uniquely ergodic if and only if an associated functional equation has no non trivial solution.—We introduce here a generalization of unique ergodicity (which appears quite naturally when studying well distributed sequences) and prove about it the same kind of results.     

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.     

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.     

Uniform estimates of (λ, ϕ)-strong integral average deviations of fourier operators

We obtain estimates of (, )-strong integral average deviations of Fourier operators on classes M defined by A. I. Stepanetz.Translated from Ukrainskii Matematicheskii Zhurnal, Vo. 42, No. 10, pp. 1434–1441, October, 1990.