graph of a graph. To be precise, we say that H is (n, e)-unavoidable if any graph with n vertices and e edges contains H as a subgraph. For example, any n-vertex graph is (n, (2))-unavoidable (since there is only one graph with n vertices and (edges and that graph includes all possible edges). Also, a d-rayed star is (n, n(d 1) + 1)-unavoidable, where (n,{n(d n> d+1 and n must be even if d is even (Fig. 8). Many beautiful results on unavoidable graphs have been proved in recent years; indeed, that subject is developing, primarily under the leadership of F. R. K. Chung, into a central area of graph theory. We mention finally the concept of a universal graph, a concept related to that of an unavoidable graph and one motivated in part by the problem of finding Ulam decompositions. If F is a family of graphs, we say that a graph G is F-universal if every F F occurs as a subgraph of G. The connection between these two ideas is the following. Let G denote the complementary graph of the graph G; that is, G is a graph with the same vertices as G and exactly (and only) the edges that G does not have. Thus, for a graph with n vertices, Fig. 7. By considering the graphs G1 (a 9k2. rayed star), G2 (3k2 disjoint triangles), and G3 (13k(3k + 1) disjoint edges and a 3k-sided polygon with each vertex connected to every other), one can deduce that U1⁄2(n) is equal to or greater than about n. (The graphs shown here illustrate the case k = 2.) 119 That result, and many other similar results (which have interesting applications to the design of VLSI chips, for example) can be found in Chung and Graham 1978, 1979, 1983; Chung, Graham, and Pippenger 1978; Bhatt and Leighton 1984; and Bhatt and Ipsen 1985. The basic idea here is that a silicon chip (or wafer) can have a universal graph G for some class of graphs, say for all trees with twenty vertices. When a particular tree T is needed for connecting various components on the chip, the appropriate edges of G can be "activated" to realize T. n the spirit of the current algorithmic trend in mathematics, we might ask how hard it is in practice to find the minimuml Ulam decomposition for two graphs G and G'. In general that is almost surely a difficult computational problem. More precisely, the question "Is U (G, G') = 2?" has been shown (Yao 1979) to belong to the notorious class of NP-complete problems, an intensively studied collection of thousands of computational problems, including the wellknown traveling salesman and graph coloring problems (see Garey and Johnson 1979). Computer scientists believe, although no one has yet been able to prove, that an NP-complete problem is inherently intractable as the general instance size of the problem increases. The resolution of that question remains as perhaps the outstanding problem in theoretical computer science. It's interesting to note that the related question "Is U(G,G') = 1?" (or "Is GG'?") is not known to belong to the class of NP-complete problems, and indeed, many people believe that an efficient algorithm does exist for its solution. A fuller treatment of such matters can be found in Garey and Johnson. conclusion, all of the preceding questions can also be asked about numerous other combinatorial and algebraic structures, such as directed graphs, hypergraphs, partially ordered sets, finite metric spaces, and so on. Some work on those topics can be found in Chung, Graham, and Erdös 1981; Chung, Graham, and Shearer 1981; Babai, Chung, Erdös, Graham, and Spencer 1982; Chung, Erdös, and Graham 1982; Chung 1983; and Chung and Erdös 1983. Clearly, however, that area of research remains mostly unexplored and is one more example of the prolific mathematical legacy left to us by Stan Ulam. F. R. K. Chung, R. L. Graham, and N. Pippenger. 1978. On graphs which contain all small trees, II. In Combinatorics, edited by A. Hajnal and Vera T. Sós, 213-223. Amsterdam: North-Holland Publishing Company. F. R. K. Chung, P. Erdös, R. L. Graham, S. M. Ulam, and F. F. Yao. 1979. Minimal decompositions of two graphs into pairwise isomorphic subgraphs. In Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic University, Boca Raton, Florida, April 2-6, 1979), 3-18. Congressus Numerantium, volume 23. Winnipeg, Manitoba: Utilitas Mathematica Publishing Incorporated. F. R. K. Chung and R. L. Graham. 1979. On universal graphs. Annals of the New York Academy of Sciences 319: 136-140. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company. F. Frances Yao. 1979. Graph 2-isomorphism is NPcomplete. Information Processing Letters 9: 68-72. F. R. K. Chung, P. Erdös, and R. L. Graham. 1981. Minimal decompositions of graphs into mutually isomorphic subgraphs. Combinatorica 1: 13-24. F. R. K. Chung, R. L. Graham, and J. Shearer. 1981. Universal caterpillars. Journal of Combinatorial Theory, Series B 31: 348-355. Ronald L. Graham received his Ph.D. in mathematics from the University of California, Berkeley. He is currently Director of the Mathematical Sciences Research Center at AT&T Bell Laboratories and University Professor of Mathematical Sciences at Rutgers University. He is a member of the National Academy of Sciences and a Fellow of the American Academy of Arts and Sciences. He has held visiting faculty positions at the University of California, Stanford University, the California Institute of Technology, and Princeton University. His professional interests include combinatorics, graph theory, number theory, geometry, and various areas of theoretical computer science. He is the author of Rudiments of Ramsey Theory (American Mathematical Society, 1981) and the co-author (with Bruce L. Rothschild and Joel H. Spencer) of Ramsey Theory (John Wiley & Sons, 1980) and (with P. Erdös) of Old and New Problems and Results in Combinatorial Number Theory (L'Enseignement Mathématique, Université de Genève, 1980). He also likes to point out that he is a Past President of the International Jugglers Association. L. Babai, F. R. K. Chung, P. Erdös, R. L. Graham, and J. Spencer. 1982. On graphs which contain all sparse graphs. Annals of Discrete Mathematics 12:21-26. F. R. K. Chung, P. Erdös, and R. L. Graham. 1982. Minimal decompositions of hypergraphs into mutually isomorphic subhypergraphs. Journal of Combinatorial Theory, Series A 32: 241-251. F. R. K. Chung. 1983. Unavoidable stars in 3graphs. Journal of Combinatorial Theory, Series A 35:252-262. F. R. K. Chung and P. Erdös. 1983. On unavoidable graphs. Combinatorica 3: 167-176. F. R. K. Chung and R. L. Graham. 1983. On universal graphs for spanning trees. Journal of the London Mathematical Society, Second Series 27: 203211. David Sankoff and Joseph B. Kruskal, editors. 1983. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Reading, Massachusetts: Addison-Wesley Publishing Company. S. N. Bhatt and F. T. Leighton. 1984. A framework for solving VLSI graph layout problems. Journal of Computer and System Sciences 28: 300-343. F. R. K. Chung, P. Erdös, and R. L. Graham. 1984. Minimal decomposition of all graphs with equinumerous vertices and edges into mutually isomorphic subgraphs. In Finite and Infinite Sets, edited by A. Hajnal, L. Lovász, and V. T. Sós, 171-179. Amsterdam: North-Holland Publishing Company. S. N. Bhatt and I. Ipsen. 1985. Embedding trees in the hypercube. Yale University Research Report RR-443. PHYSICS "Because of the novel problems which confronted its scientists dur- Problems of a complexity surpassing anything that had ever existed in technology rendered imperative the development of electronic computing machines and the invention of new theoret ical computing methods. There, consultants like von Neumann played an important role in helping enlarge the horizon of the innovations, which required the most abstract ideas derived from the foundations of mathematics as well as from theoretical physics. [These ideas] were and still are invested in new, fruitful ways.... In at least two different and separate ways the availability of computing machines has enlarged the scope of mathematical research. It has enabled us ... to gather through heuristic experiments impressions of the morphological nature of various mathematical concepts such as the behaviour ... of certain non-linear transformations, the properties of some combinatorial systems and some topological curiosities of seemingly general behaviours. It has also enabled us to throw light on the behaviour of ... complicated systems .. [through] Monte Carlo type experiments and extensive but 'intelligently chosen' brute force approaches, in hydrodynamics for example." S. Ulam 1984 he remarks at left, written to preface Ulam's collected Los Alamos reports, suggest The context, the content, and import of his influence at Los Alamos report on the hydrogen bomb, written with Edward Teller, is certainly of great interest, but classification precludes any discussion beyond that found in "Vita” and "From Above the Fray" in Part I. Weapons development, however, was only one among many Los Alamos projects in which Stan had a hand. In fact the list of his publications at the back of this volume reads in many parts like a history of ideas at Los Alamos. The reports authored by Stan and his many illustrious collaborators on the Monte Carlo method, hydrodynamics, nonlinear transformations, computer studies of nonlinear systems, and other diverse topics, as well as his informal talks and conversations, have left a legacy of ideas and possibilities that are still only partially explored. Stan was present at the opening of the computing era, and together with von Neumann, he understood perhaps better than others its revolutionary potential for exploring complex systems of all kinds. Nick Metropolis, in "The Beginning of the Monte Carlo Method," describes from firsthand experience the early years of the computer revolution and the invention and first applications of the Monte Carlo method. As the name implies, this method turns an iterative process (such as a neutron chain reaction or repeated application of a deterministic transformation) into a game of chance. The computer plays the game over and over again to obtain good estimates of the average (or asymptotic) outcome of the process. In his 1950 paper "Random Processes and Transformations" Ulam outlined a variety of ways in which deterministic problems in mathematics and physics could be converted into equivalent random processes, or games of chance. His vision was prophetic and this method has taken hold in many areas; even particle physicists are applying Monte Carlo techniques to find solutions to complex problems in quantum field theory. While Metropolis's article and the others on Monte Carlo are basically review, the remaining articles in this section describe current research on nonlinear systems whose inspiration or approach relate back to Stan. In each case computer experiments are used to gain insight into complex behavior. Turbulence, the chaotic flow we observe in streams and waterfalls, in the oceans, and in the atmosphere, is one of the most difficult problems in nonlinear science. It has defied a fundamental description by mathematicians and physicists for over a hundred years, but its effects must be modeled if we are to achieve success in many technological programs. In this issue two articles deal with attempts to model this phenomenon by computer simulation. "Instabilities and Turbulence" by Frank Harlow and his collaborators introduces us to the nature of turbulence, describes its disruptive effects in technological applications, and presents a new theory of turbulence transport that strips away the fine-scale details |