Search

The size Ramsey number r(G, H) of graphs G and H is the smallest integer r such that there is a graph F with r edges and if the edge set of F is red‐blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r(Tnd, Tnd) ⩽ c · d2 · n and c · n3 ⩽ r(Kn, Tnd) ⩽ c(d)·n3 log n for every tree Tnd on n vertices. and maximal degree at most d and a complete graph Kn on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc. © 1993 Wiley Periodicals, Inc.

In this paper we analyze: (i) a storage allocation algorithm (D.E. Knuth, The Art of Computer Programming-Vol. I, Addison-Wesley, Reading, MA, 1969, Ex. 2.2.2.13) which permits one to maintain two stacks inside a shared (continuous) memory area of a fixed size, and (ii) the well-known banker algorithm which plays a fundamental role in parallel processing (J. Francon, Combinatoire et Parallelisme; Journees Informatique et Mathematique; Lumigny, October 15-17, 1987; A. N. Habermann, in Current Trends in Programming Methodology, Vol. 3, K. M. Chandy and R. T. Yeh, Eds., Prentice-Hall, Englewood Cliffs, NJ, 1987; J. Peterson and A. Silberschatz, Operating Systems Concepts, Addison-Wesley, Reading, MA, 1983). The natural formulation of the problems to be solved here is in terms of random walks. For (i) the random walk Ym(-) takes place in a triangle in a two-dimensional lattice space with two reflecting barriers along the axes (a deletion has no effect on an empty stack) and one absorbing barrier along the diagonal (the algorithm stops when the combined sizes of the stacks exhaust the available storage). For (ii) the random walk takes place in a rectangle with broken corner and has four reflecting barriers and one absorbing barrier (see Fig. 10). With the help of diffusion techniques, we obtain, asymptotically as m: ∞. the distributions of the hitting place (Zm) and hitting time (Tm) on the absorbing boundary. the joint distribution of Zm and Tm. the distribution P[Ym(n) ≦ ym, n < Tm].

A set of natural numbers is called an asymptotic basis of order k if every number (sufficiently large) can be expressed as a sum of k distinct numbers from the set. in this paper we prove that, for every fixed k, there exists an asymptotic basis of order k such that the number of representations of n is Θ(log n). © 1990 Wiley Periodicals, Inc.

The van der Waerden number W(n) is the smallest integer so that if we divide the integers {1,2, …, W(n)} into two classes, then at least one of them contains an arithmetic progression of length n. We prove in this paper that W(n) ≥ 2n/nϵ for all sufficiently large n. © 1990 Wiley Periodicals, Inc.

A famous result of Rado characterises those integer matrices $A$ which are partition regular, i.e. for which any finite colouring of the positive integers gives rise to a monochromatic solution to the equation $Ax=0$. Aigner-Horev and Person recently stated a conjecture on the probability threshold for the binomial random set $[n]_p$ having the asymmetric random Rado property: given partition regular matrices $A_1, \dots, A_r$ (for a fixed $r \geq 2$), however one $r$-colours $[n]_p$, there is always a colour $i \in [r]$ such that there is an $i$-coloured solution to $A_i x=0$. This generalises the symmetric case, which was resolved by R\"odl and Ruci\'nski, and Friedgut, R\"odl and Schacht. Aigner-Horev and Person proved the $1$-statement of their asymmetric conjecture. In this paper, we resolve the $0$-statement in the case where the $A_i x=0$ correspond to single linear equations. Additionally we close a gap in the original proof of the 0-statement of the (symmetric) random Rado theorem., Comment: 20 pages, 4 figures, author accepted version, to appear in Random Structures and Algorithms