Diskret matematik

Combinatorial enumeration is a readily accessible subject full of easily stated, but sometimes tantalizingly difficult problems. This book leads the reader in a leisurely way from the basic notions to a variety of topics, ranging from algebra to statistical physics. Its aim is to introduce the student to a fascinating field, and to be a source of information for the professional mathematician who wants to learn more about the subject. The book is organized in three parts: Basics, Methods, and Topics. There are 666 exercises, and as a special feature every chapter ends with a highlight, discussing a particularly beautiful or famous result.

The problem of "e;Shortest Connectivity"e;, which is discussed here, has a long and convoluted history. Many scientists from many fields as well as laymen have stepped on its stage. Usually, the problem is known as Steiner's Problem and it can be described more precisely in the following way: Given a finite set of points in a metric space, search for a network that connects these points with the shortest possible length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. Steiner's Problem seems disarmingly simple, but it is rich with possibilities and difficulties, even in the simplest case, the Euclidean plane. This is one of the reasons that an enormous volume of literature has been published, starting in 1 the seventeenth century and continuing until today. The difficulty is that we look for the shortest network overall. Minimum span- ning networks have been well-studied and solved eompletely in the case where only the given points must be connected. The novelty of Steiner's Problem is that new points, the Steiner points, may be introduced so that an intercon- necting network of all these points will be shorter. This also shows that it is impossible to solve the problem with combinatorial and geometric methods alone.

Invariant, or coordinate-free methods provide a natural framework for many geometric questions. Invariant Methods in Discrete and Computational Geometry provides a basic introduction to several aspects of invariant theory, including the supersymmetric algebra, the Grassmann-Cayler algebra, and Chow forms. It also presents a number of current research papers on invariant theory and its applications to problems in geometry, such as automated theorem proving and computer vision. Audience: Researchers studying mathematics, computers and robotics.

The last decade has seen two parallel developments, one in computer science, the other in mathematics, both dealing with the same kind of combinatorial structures: networks with strong symmetry properties or, in graph-theoretical language, vertex-transitive graphs, in particular their prototypical examples, Cayley graphs. In the design of large interconnection networks it was realised that many of the most fre- quently used models for such networks are Cayley graphs of various well-known groups. This has spawned a considerable amount of activity in the study of the combinatorial properties of such graphs. A number of symposia and congresses (such as the bi-annual IWIN, starting in 1991) bear witness to the interest of the computer science community in this subject. On the mathematical side, and independently of any interest in applications, progress in group theory has made it possible to make a realistic attempt at a complete description of vertex-transitive graphs. The classification of the finite simple groups has played an important role in this respect.

Although the ?rst decades of the 20th century saw some strong debates on set theory and the foundation of mathematics, afterwards set theory has turned into a solid branch of mathematics, indeed, so solid, that it serves as the foundation of the whole building of mathematics. Later generations, honest to Hilbert's dictum, "e;No one can chase us out of the paradise that Cantor has created for us"e; proved countless deep and interesting theorems and also applied the methods of set theory to various problems in algebra, topology, in?nitary combinatorics, and real analysis. The invention of forcing produced a powerful, technically sophisticated tool for solving unsolvable problems. Still, most results of the pre-Cohen era can be digested with just the knowledge of a commonsense introduction to the topic. And it is a worthy e?ort, here we refer not just to usefulness, but, ?rst and foremost, to mathematical beauty. In this volume we o?er a collection of various problems in set theory. Most of classical set theory is covered, classical in the sense that independence methods are not used, but classical also in the sense that most results come fromtheperiod,say,1920-1970.Manyproblemsarealsorelatedtoother?elds of mathematics such as algebra, combinatorics, topology, and real analysis. We do not concentrate on the axiomatic framework, although some - pects, such as the axiom of foundation or the role E of the axiom of choice, are elaborated.

This book contains 28 research articles from among the 49 papers and abstracts presented at the Tenth International Conference on Fibonacci Numbers and Their Applications. These articles have been selected after a careful review by expert referees, and they range over many areas of mathematics. The Fibonacci numbers and recurrence relations are their unifying bond. We note that the article "e;Fibonacci, Vern and Dan"e; , which follows the Introduction to this volume, is not a research paper. It is a personal reminiscence by Marjorie Bicknell-Johnson, a longtime member of the Fibonacci Association. The editor believes it will be of interest to all readers. It is anticipated that this book, like the eight predecessors, will be useful to research workers and students at all levels who are interested in the Fibonacci numbers and their applications. March 16, 2003 The Editor Fredric T. Howard Mathematics Department Wake Forest University Box 7388 Reynolda Station Winston-Salem, NC 27109 xxi THE ORGANIZING COMMITTEES LOCAL COMMITTEE INTERNATIONAL COMMITTEE Calvin Long, Chairman A. F. Horadam (Australia), Co-Chair Terry Crites A. N. Philippou (Cyprus), Co-Chair Steven Wilson A. Adelberg (U. S. A. ) C. Cooper (U. S. A. ) Jeff Rushal H. Harborth (Germany) Y. Horibe (Japan) M. Bicknell-Johnson (U. S. A. ) P. Kiss (Hungary) J. Lahr (Luxembourg) G. M. Phillips (Scotland) J. 'Thrner (New Zealand) xxiii xxiv LIST OF CONTRlBUTORS TO THE CONFERENCE * ADELBERG, ARNOLD, "e;Universal Bernoulli Polynomials and p-adic Congruences. "e; *AGRATINI, OCTAVIAN, "e;A Generalization of Durrmeyer-Type Polynomials. "e; BENJAMIN, ART, "e;Mathemagics.

In the last years, it was observed an increasing interest of computer scientists in the structure of biological molecules and the way how they can be manipulated in vitro in order to define theoretical models of computation based on genetic engineering tools. Along the same lines, a parallel interest is growing regarding the process of evolution of living organisms. Much of the current data for genomes are expressed in the form of maps which are now becoming available and permit the study of the evolution of organisms at the scale of genome for the first time. On the other hand, there is an active trend nowadays throughout the field of computational biology toward abstracted, hierarchical views of biological sequences, which is very much in the spirit of computational linguistics. In the last decades, results and methods in the field of formal language theory that might be applied to the description of biological sequences were pointed out.