Page images
[blocks in formation]

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, ())-unavoidable (since there is only one graph with n vertices and (2) edges and that graph includes all possible edges). Also, a d-rayed star is (n, {n(d − 1) + 1)-unavoidable, where n> d + 1 and n must be even if d is even (Fig. 8). Many beautiful results on unavoidable graphs have been proved in

[merged small][merged small][merged small][merged small][ocr errors][ocr errors]

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 FF 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,

e(G) + e(Ğ) = (n)

Now if F(i,j) denotes the family of all graphs with i vertices and j edges, then the statement


e = 9k2, n = 3k(3k+2)

U(G1, G2, G3) =

e(G2) = 9k2 n(G2)=9k2

[ocr errors][merged small]

is equivalent to the statement

Ĥ is F(n, (2) − e)-universal. Figure 9 illustrates this equivalence.

Much is now known about F-universal graphs for special classes of F. For example, if F = T2, the family of all trees (connected graphs containing no closed loops) with n vertices, then the minimum possible number s(T) of edges in a Tuniversal graph satisfies


[ocr errors]

His (n, e)-unavoidable

[blocks in formation]

e(G3) = 3k(3k − 1) + 13k(3k − 1) = 9k2

-- ·

n(G3) = 3k+3k(3k + 1) = 3k(3k + 2)

k(3k -1)+k(3k + 1) = (9k2 + k)

if k = 4j or 4j-1

k(3k-1)+k(3k + 1) + 1 = (9k2 + k) + 1⁄2 otherwise

[merged small][ocr errors][merged small][merged small]


star is (6,10)-unavoidable

[merged small][merged small][ocr errors][merged small]

H is 6, 10)-unavoidable

unavoidable; that is, any graph with 6 vertices
and 10 edges contains H as a subgraph (see
Fig. 8). Therefore Ĥ is F(6, 5)-universal; that is,
any graph with 6 vertices and 5 edges (such as
a 5-rayed star) is contained in Ĥ.

[ocr errors]

Ĥ is F(6,5)-universal

Fig. 8. (a) Since a 3-rayed star is (4,5)-unavoidable, it is a subgraph of the single graph with 4 vertices and 5 edges. (b) Since a 4-rayed star is (6,10)-unavoidable, it is a subgraph of all four of the graphs with 6 vertices and 10 edges. (c) Since a 5-rayed star is not (6,12)unavoidable, it is not a subgraph of some graph with 6 vertices and 12 edges.

That result, and many other similar re-
sults (which have interesting applications
to the design of VLSI chips, for exam-
ple) can be found in Chung and Gra-
ham 1978, 1979, 1983; Chung, Graham,
and Pippenger 1978; Bhatt and Leighton
1984; and Bhatt and Ipsen 1985.
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 compo-
nents 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 ques


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. ■

[blocks in formation]

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.




Shaye 98524398508

[ocr errors]
[ocr errors]
[ocr errors]
[ocr errors]
[ocr errors]
[ocr errors]
[ocr errors]
[ocr errors]

"Because of the novel problems which confronted its scientists during the wartime establishment of Los Alamos, the need arose for research and ideas in domains contiguous to its central purpose. This trend continues unabated to the present.

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 theoretical 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 the import of his influence at Los Alamos. The 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


« PreviousContinue »