On the Value of a Random Minimum Weight Steiner Tree

Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center.     

On a Problem of Cameron’s on Inexhaustible Graphs

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.The authors gratefully acknowledge support from the Natural Science and Engineering Research Council of Canada (NSERC).     

Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders

We consider the poset SO(n) of all words over an n-element alphabet ordered by the subword relation. It is known that SO(2) falls into the class of Macaulay posets, i. e. there is a theorem of Kruskal–Katona type for SO(2). As the corresponding linear ordering of the elements of SO(2) the vip-order can be chosen.Daykin introduced the V-order which generalizes the vip-order to the n2 case. He conjectured that the V-order gives a Kruskal–Katona type theorem for SO(n).We show that this conjecture fails for all n3 by explicitly giving a counterexample. Based on this, we prove that for no n3 the subword order SO(n) is a Macaulay poset.     

The Diameter of a Scale-Free Random Graph

We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately logn. We show that while this holds for m=1, for m2 the diameter is asymptotically log n/log logn.* Research supported in part by NSF grant no. DSM9971788     

Triangle Factors In Sparse Pseudo-Random Graphs

The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd ³/n ² log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d ²/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich.     

On Graphs With Small Ramsey Numbers,II

There exists a constant C such that for every d-degenerate graphs G ₁ and G ₂ on n vertices, Ramsey number R(G ₁,G ₂) is at most Cn, where is the minimum of the maximum degrees of G ₁ and G ₂.* The work of this author was supported by the grants 99-01-00581 and 00-01-00916 of the Russian Foundation for Fundamental Research and the Dutch-Russian Grant NWO-047-008-006. The work of this author was supported by the NSF grant DMS-9704114.     

Arithmetic Properties of Non-Squashing Partitions into Distinct Parts

A partition with is non-squashing if On their way towards the solution of a certain box-stacking problem, Sloane and Sellers were led to consider the number b(n) of non-squashing partitions of n into distinct parts. Sloane and Sellers did briefly consider congruences for b(n) modulo 2. In this paper we show that 2^r-2 is the exact power of 2 dividing the difference b(2^r+1n)–b(2^r-1n) for n odd and r 2.     

Positive Operator Majorization and <Emphasis Type="Italic">p</Emphasis>-hyponormality

In this note we examine the relationships between p-hyponormal operators and the operator inequality . This leads to a method for generating examples of p-hyponormal operators which are not q-hyponormal for any . Our methods are also shown to have implications for the class of Furuta type inequalities.     

The Volterra Operator is not Supercyclic

It is shown that the classical Volterra operator, which is cyclic, is not supercyclic on any of the spaces L^p[0, 1], 1 p < . This solves a question posed by Héctor Salas. This contrasts with the fact that the derivative operator, the left inverse of the Volterra operator, although unbounded, is hypercyclic on L^p[0, 1].     

Formulas for the Inverses of Toeplitz Matrices with Polynomially Singular Symbols

We consider large finite Toeplitz matrices with symbols of the form (1– cos )^p f() where p is a natural number and f is a sufficiently smooth positive function. By employing techniques based on the use of predictor polynomials, we derive exact and asymptotic formulas for the entries of the inverses of these matrices. We show in particular that asymptotically the inverse matrix mimics the Green kernel of a boundary value problem for the differential operator Submitted: June 20, 2003