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.     

Star chromatic numbers of graphs

We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Asymptotic limit law for the close approach of two trajectories in expanding maps of the circle

Summary Given two pointsx, yS ¹ randomly chosen independently by a mixing absolutely continuous invariant measure of a piecewise expanding and smooth mapf of the circle, we consider for each >0 the point process obtained by recording the timesn>0 such that |f ⁿ (x)–f ⁿ (y)|. With the further assumption that the density of is bounded away from zero, we show that when tends to zero the above point process scaled by –1 converges in law to a marked Poisson point process with constant parameter measure. This parameter measure is given explicity by an average on the rate of expansion off.Partially supported by FAPESP grant number 90/3918-5     

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     

Periodic optimal control in Hilbert space

Optimal control problem governed byy=Ay + Bu, y(0)=y (T), =±1 are studied, whereA is the infinitesimal generator of a nonasymptotically stableC _o semigroup andB is a linear operator from a controller spaceU into a state spaceH. Both distributed (B L(U, H)) and boundary cases (B L(U, (D(A ^*)))) are investigated. Some applications to periodic control of wave equations are given.This work was supported by the National Science Foundation under Grant No. DMS-91-11794.     

Generation of alternating groups by pairs of conjugates

Considering the conjugacy classes of the alternating group of degreen, those classes that contain a pair of generators are in the majority. In fact, the proportion of such classes is 1 –(n), and(n) 0 asn .     

A geometric construction of the K-loop of a hyperbolic space

It is well known that the homogeneous orthochronous proper Lorentzgroup is isomorphic to the proper motion group of the hyperbolic space. To each Lorentz boost \ {id} there corresponds in the hyperbolic space exactly one lineL such that fixes each of the two ends ofL . Furthermore has no fixed points but each plane containingL is fixed by . If we fix a pointo, then to each other pointa there is exactly one boosta ⁺ such thatL _a+ is the line joiningo anda anda ⁺(o)=a. The set P of points of the hyperbolic space is turned in a K-loop (P, +) bya+b:=a ⁺(b). Each line of the hyperbolic space has the representationa+Z(b) wherea, b P,b 0 andZ(b):= {x P |x+b=b+x}.Dedicated to H. Salzmann on the occasion of his 65th birthdaySupported by the NATO Scientific Affairs Division grant CRG 900103.     

(g,f)-Factorizations of graphs orthogonal to [1,2]-subgraph

LetG be a simple graph. Letg(x) andf(x) be integer-valued functions defined onV(G) withf(x)g(x)1 for allxV(G). It is proved that ifG is an (mg+m–1,mf–m+1)-graph andH is a [1,2]-subgraph withm edges, then there exists a (g,f)-factorization ofG orthogonal toH.This work is supported by China Postdoctoral Science Foundation and Shandong Youth Science Foundation.     

Stability of Bounded Solutions of Differential Equations with Small Parameter in a Banach Space

For a sectorial operator A with spectrum (A) that acts in a complex Banach space B, we prove that the condition (A) i R = Ø is sufficient for the differential equation where is a small positive parameter, to have a unique bounded solution x for an arbitrary bounded function f: R B that satisfies a certain Hölder condition. We also establish that bounded solutions of these equations converge uniformly on R as 0+ to the unique bounded solution of the differential equation x(t) = Ax(t) + f(t).     

Characterization of complete exterior sets of conics

Let be a set of exterior points of a nondegenerate conic inPG(2,q) with the property that the line joining any 2 points in misses the conic. Ifq1 (mod 4) then consists of the exterior points on a passant, ifq3 (mod 4) then other examples exist (at least forq=7, 11, ..., 31).Support from the Dutch organization for scientific Research (NWO) is gratefully acknowledged     

Difference sets and inverting the difference operator

For a setA of non-negative numbers, letD(A) (the difference set ofA) be the set of nonnegative differences of elements ofA, and letD ^k be thek-fold iteration ofD. We show that for everyk, almost every set of non-negative integers containing 0 arises asD ^k (A) for someA. We also give sufficient conditions for a setA to be the unique setX such that 0X andD ^k (X)=D ^k (A). We show that for eachm there is a setA such thatD(X)=D(A) has exactly 2 ^m solutionsX with 0X.This work was supported by grants DMS 92-02833 and DMS 91-23478 from the National Science Foundation. The first author acknowledges the support of the Hungarian National Science Foundation under grants, OTKA 4269, and OTKA 016389, and the National Security Agency (grant No. MDA904-95-H-1045).Lee A. Rubel died March 25, 1995. He is very much missed by his coauthors.     

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.     

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.     

Comparison results for the lower tail of Gaussian seminorms

Let =( _n ) be i.i.d.N(0, 1) random variables andq(x), q(x):R [0, ) be seminorms. We investigate necessary and sufficient conditions that the ratio ofP(q()<) andP(q()<) goes to a positive constant as 0⁺. We give satisfactory answers forl ₂-norms and also some results for sup-norms andl _p-norms. Some applications are given to the rate of escape of infinite dimensional Brownian motion, and we give the lower tail of the Ornstein-Uhlenbeck process and a weighted Brownian bridge under theL ₂-norms.     

S-Continued Fraction Method for the Investigation of a Complex Dielectric Constant of Two-Components Composite

The aim of this contribution is to examine the S-continued fraction method of obtaining bounds on the effective dielectric constant _e of a two-phase composite for the case where the dielectric coefficients ₁and ₂ of both components are either complex or real. The starting point for our study is a power expansion of _e (z) at(z)=0 (z)=₂/₁-1. The obtained S-continued fraction bounds have an interesting mathematical structure convenient for theoretical and numerical investigations of _e. They also agree with the earlier estimations reported by Bergman and Milton. Specific examples of calculation of bounds on _e by theS-continued fraction method are also provided.     

An infinite dimensional analogue of the Albeverio-Röckner's theorem on Fukushima's conjecture

LetX be the solution of the SDE:dX _t = (X _t)dB _t +b(X _t)dt, with andb C _b (R) such that >0 for some constant , andB a real Brownian motion. Let be the law ofX onE=C([0, 1],R) andk E* – {0}, whereE* is the topological dual space ofE. Consider the classical form: _k (u, v)=u / kv / kd, whereu andv are smooth functions onE. We prove that, if _k is closable for anyk in a dense subset ofE* and if the smooth functions are contained in the domain of the generator of the closure of _k , must be a constant function.     

Circle grids and bipartite graphs of distances

Fort fixed,n+t pointsA ₁,A ₂,...,A _n andB ₁,B ₂,...,B _t are constructed in the plane withO(n) distinct distancesd(A _i B _j ) As a by-product we show that the graph of thek largest distances can contain a complete subgraphK _{t, n} withn=(k ²), which settles a problem of Erds, Lovász and Vesztergombi.Research partially supported by the Hungarian National Science Fund (OTKA) # 2117.     

On depth first search strees inm-out digraphs

We consider depth first search (DFS for short) trees in a class of random digraphs: am-out model. Let _i be thei ^th vertex encountered by DFS andL(i, m, n) be the height of _i in the corresponding DFS tree. We show that ifi/n asn, then there exists a constanta(,m), to be defined later, such thatL(i, m, n)/n converges in probability toa(,m) asn. We also obtain results concerning the number of vertices and the number of leaves in a DFS tree.     

A-stable spline-collocation methods of multivalue type

In this paper the general classV of spline-collocation methods presented by Mülthei is investigated. The methods ofV approximate solutions of first order initial value problems. ClassV contains as subclass the methods of so-called multivalue type, and in particular contains the generalized singly-implicit methods treated by Butcher.Any multivalue type representativeU V yields a matrix valued function corresponding toU, which characterizes the region of absolute stability ofU. If a sequence (U()) of multivalue type representatives ofV tending to some singlevalue type representative V is considered, it can easily be seen by the structure of , that the sequence of the greatest eigenvalues of the (.,) tends to the stability function corresponding to . This fact allows one to construct one-parameter families of A-stable methods of multivalue type.