This book contains contributions from a workshop on topology and geometry of polymers, held at the IMA in June 1996, which brought together topologists, combinatorialists, theoretical physicists and polymer scientists, with a common interest in polymer topology. Polymers can be highly self-entangled even in dilute solution. In the melt the inter- and intra-chain entanglements can dominate the rheological properties of these phenomena. Although the possibility of knotting in ring polymers has been recognized for more than thirty years it is only recently that the powerful methods of algebraic topology have been used in treating models of polymers. This book contains a series of chapters which review the current state of the field and give an up to date account of what is known and perhaps more importantly, what is still unknown. The field abounds with open problems. The book is of interest to workers in polymer statistical mechanics but will also be useful as an introduction to topological methods for polymer scientists, and will introduce mathematicians to an area of science where topological approaches are making a substantial contribution.

This book contains 50 papers from among the 95 papers presented at the Seventh International Conference on Fibonacci Numbers and Their Applications which was held at the Institut Fiir Mathematik, Technische Universitiit Graz, Steyrergasse 30, A-SOlO Graz, Austria, from July 15 to July 19, 1996. These papers have been selected after a careful review by well known referees in the field, and they range from elementary number theory to probability and statistics. The Fibonacci numbers and recurrence relations are their unifying bond. It is anticipated that this book, like its six predecessors, will be useful to research workers and graduate students interested in the Fibonacci numbers and their applications. September 1, 1997 The Editors Gerald E. Bergum South Dakota State University Brookings, South Dakota, U. S. A. Alwyn F. Horadam University of New England Armidale, N. S. W. , Australia Andreas N. Philippou House of Representatives Nicosia, Cyprus xxvii THE ORGANIZING COMMITTEES LOCAL COMMITTEE INTERNATIONAL COMMITTEE Tichy, Robert, Chairman Horadam, A. F. (Australia), Co-Chair Prodinger, Helmut, Co-Chairman Philippou, A. N. (Cyprus), Co-Chair Grabner, Peter Bergurt:t, G. E. (U. S. A. ) Kirschenhofer, Peter Filipponi, P. (Italy) Harborth, H. (Germany) Horibe, Y. (Japan) Johnson, M. (U. S. A. ) Kiss, P. (Hungary) Phillips, G. M. (Scotland) Turner, J. (New Zealand) Waddill, M. E. (U. S. A. ) xxix LIST OF CONTRIBUTORS TO THE CONFERENCE *ADELBERG, ARNOLD, "Higher Order Bernoulli Polynomials and Newton Polygons. " AMMANN, ANDRE, "Associated Fibonacci Sequences. " *ANDERSON, PETER G. , "The Fibonacci Shuffle Tree.

This book contains translations of papers from the second volume of the new Russian-language journal published at the Sobolev Institute of Mathematics (Sibe- rian Branch of the Russian Academy of Sciences, Novosibirsk) since 1994. In 1994 the journal was titled Sibirskil Zhurnal Issledovaniya Oper- atsil. Since 1995 this journal has the title Diskretny'l Analiz i Issledovanie Operatsi'l (Discrete Analysis and Operations Research). The aim of this journal is to bring together research papers in different areas of discrete mathematics and computer science. The journal DiskretnYl Analiz i Issledovanie Operatsil covers the following fields: * discrete optimization * synthesis and complexity * discrete structures and * of control systems extremal problems * automata * combinatorics * graphs * control and reliability * game theory and its of discrete devices applications * mathematical models and * coding theory methods of decision making * scheduling theory * design and analysis * functional systems theory of algorithms Contributions presented to the journal can be original research papers and occasional survey articles of moderate length. The journal is published in one volume of four issues per year that appear in March, June, September, and December. Each volume contains approximately 400 pages. I express my sincere gratitude to Professor S. S. Kutateladze for his help in editing the English translation.

Asymptotic Combinatorial Coding Theory is devoted to the investigation of the combinatorial properties of transmission systems using discrete signals. The book presents results of interest to specialists in combinatorics seeking to apply combinatorial methods to problems of combinatorial coding theory. Asymptotic Combinatorial Coding Theory serves as an excellent reference for resarchers in discrete mathematics, combinatorics, and combinatorial coding theory, and may be used as a text for advanced courses on the subject.

Itgivesmegreatpleasuretoeditthisbook. Thegenesisofthisbookgoes backtotheconferenceheldattheUniversityofBolognainJune1999,on collaborativeworkbetweentheUniversityofCaliforniaatBerkeleyandthe UniversityofBologna. Theoriginalideawastoinvitesomespeakersatthe conferencetosubmitarticlestothebook. Thescopeofthebookwaslater- hancedand,inthepresentform,itisacompilationofsomeoftherecentwork usinggeometricpartialdi?erentialequationsandthelevelsetmethodology inmedicalandbiomedicalimageanalysis. Thesynopsisofthebookisasfollows:Inthe?rstchapter,R. Malladi andJ. A. Sethianpointtotheoriginsoftheuseoflevelsetmethodsand geometricPDEsforsegmentation,andpresentfastmethodsforshapes- mentationinbothmedicalandbiomedicalimageapplications. InChapter 2,C. OrtizdeSolorzano,R. Malladi,andS. J. Lockettdescribeabodyof workthatwasdoneoverthepastcoupleofyearsattheLawrenceBerkeley NationalLaboratoryonapplicationsoflevelsetmethodsinthestudyand understandingofconfocalmicroscopeimagery. TheworkinChapter3byA. Sarti,C. Lamberti,andR. Malladiaddressestheproblemofunderstanding di?culttimevaryingechocardiographicimagery. Thisworkpresentsvarious levelsetmodelsthataredesignedto?tavarietyofimagingsituations,i. e. timevarying2D,3D,andtimevarying3D. InChapter4,L. VeseandT. F. Chanpresentasegmentationmodelwithoutedgesandalsoshowextensions totheMumford-Shahmodel. Thismodelisparticularlypowerfulincertain applicationswhencomparisonsbetweennormalandabnormalsubjectsis- quired. Next,inChapter5,A. EladandR. Kimmelusethefastmarching methodontriangulateddomaintobuildatechniquetounfoldthecortexand mapitontoasphere. Thistechniqueismotivatedinpartbynewadvances infMRIbasedneuroimaging. InChapter6,T. DeschampsandL. D. Cohen presentaminimalpathbasedmethodofgroupingconnectedcomponentsand showcleverapplicationsinvesseldetectionin3Dmedicaldata. Finally,in Chapter7,A. Sarti,K. Mikula,F. Sgallari,andC. Lamberti,describean- linearmodelfor?lteringtimevarying3Dmedicaldataandshowimpressive resultsinbothultrasoundandechoimages. IoweadebtofgratitudetoClaudioLambertiandAlessandroSartifor invitingmetoBologna,andlogisticalsupportfortheconference. Ithank thecontributingauthorsfortheirenthusiasmand?exibility,theSpringer mathematicseditorMartinPetersforhisoptimismandpatience,andJ. A. Sethianforhisunfailingsupport,goodhumor,andguidancethroughthe years. Berkeley,California R. Malladi October,2001 Contents 1 FastMethodsforShapeExtractioninMedicaland BiomedicalImaging...1 R. Malladi,J. A. Sethian 1. 1Introduction...1 1. 2TheFastMarchingMethod...3 1. 3ShapeRecoveryfromMedicalImages...6 1. 4Results...10 References...13 2 AGeometricModelforImageAnalysisinCytology...19 C. OrtizdeSolorzano,R. Malladi,,S. J. Lockett 2. 1Introduction...19 2. 2GeometricModelforImageAnalysis...20 2. 3SegmentationofNuclei...22 2. 4SegmentationofNucleiandCellsUsingMembrane-RelatedProtein Markers...31 2. 5Conclusions...37 References...38 3 LevelSetModelsforAnalysisof2Dand3D EchocardiographicData...43 A. Sarti,C. Lamberti,R. Malladi 3. 1Introduction...43 3. 2TheGeometricEvolutionEquation...45 3. 3TheShock-TypeFiltering...46 3. 4ShapeExtraction...49 3. 52DEchocardiography...52 3. 62D+timeEchocardiography...53 3. 73DEchocardiography...56 3. 83D+timeEchocardiography...58 3. 9Conclusions...59 References...61 4 ActiveContourandSegmentationModelsusing GeometricPDE'sforMedicalImaging...63 T. F. Chan,L. A. Vese 4. 1Introduction...63 4. 2DescriptionoftheModels...64 4. 3ApplicationstoBio-MedicalImages...68 4. 4ConcludingRemarks...68 References...7 0 VIII Contents 5 SphericalFlatteningoftheCortexSurface...77 A. Elad(Elbaz),R. Kimmel 5. 1Introduction...77 5. 2FastMarchingMethodonTriangulatedDomains...80 5. 3Multi-DimensionalScaling...80 5. 4CortexUnfolding...84 5. 5Conclusions...86 References...86 6 GroupingConnectedComponentsusingMinimalPath Techniques...91 T. Deschamps,L. D. Cohen 6. 1Introduction...91 6. 2MinimalPathsin2Dand3D...93 6. 3FindingContoursfromaSetofConnectedComponentsR...96 k 6. 4FindingaSetofPathsina3DImage...102 6. 5Conclusion...103 References...104 7 NonlinearMultiscaleAnalysisModelsforFilteringof 3D+TimeBiomedicalImages...107 A. Sarti,K. Mikula,F. Sgallari,C.

One of the most effective ways to stimulate students to enjoy intellectual efforts is the scientific competition. In 1894 the Hungarian Mathematical and Physical Society introduced a mathematical competition for high school students. The success of high school competitions led the Mathematical Society to found a college level contest, named after Miklos Schweitzer. The problems of the Schweitzer Contests are proposed and selected by the most prominent Hungarian mathematicians. This book collects the problems posed in the contests between 1962 and 1991 which range from algebra, combinatorics, theory of functions, geometry, measure theory, number theory, operator theory, probability theory, topology, to set theory. The second part contains the solutions. The Schweitzer competition is one of the most unique in the world. The experience shows that this competition helps to identify research talents. This collection of problems and solutions in several fields in mathematics can serve as a guide for many undergraduates and young mathematicians. The large variety of research level problems might be of interest for more mature mathematicians and historians of mathematics as well.

Most networks and databases that humans have to deal with contain large, albeit finite number of units. Their structure, for maintaining functional consistency of the components, is essentially not random and calls for a precise quantitative description of relations between nodes (or data units) and all network components. This book is an introduction, for both graduate students and newcomers to the field, to the theory of graphs and random walks on such graphs. The methods based on random walks and diffusions for exploring the structure of finite connected graphs and databases are reviewed (Markov chain analysis). This provides the necessary basis for consistently discussing a number of applications such diverse as electric resistance networks, estimation of land prices, urban planning, linguistic databases, music, and gene expression regulatory networks.

This IMA Volume in Mathematics and its Applications GRID GENERATION AND ADAPTIVE ALGORITHMS is based on the proceedings of a workshop with the same title. The work shop was an integral part of the 1996-97 IMA program on "MATHEMAT ICS IN HIGH-PERFORMANCE COMPUTING. " I would like to thank Marshall Bern (Xerox, Palo Alto Research Cen ter), Joseph E. Flaherty (Department of Computer Science, Rensselaer Polytechnic Institute), and Mitchell Luskin (School of Mathematics, Uni versity of Minnesota), for their excellent work as organizers of the meeting and for editing the proceedings. I also take this opportunity to thank the National Science Founda tion (NSF), Department of Energy (DOE), and the Army Research Office (ARO), whose financial support made the workshop possible. Willard Miller, Jr. , Professor and Director v PREFACE Scientific and engineering computation has become so complex that traditional numerical computation on uniform meshes is generally not pos sible or too expensive. Mesh generation must reflect both the domain geometry and the expected solution characteristics. Meshes should, fur thermore, be related to the solution through computable estimates of dis cretization errors. This, suggests an automatic and adaptive process where an initial mesh is enriched with the goal of computing a solution with prescribed accuracy specifications in an optimal manner. While automatic mesh generation procedures and adaptive strategies are becoming available, major computational challenges remain. Three-dimensional mesh genera tion is still far from automatic.

The articles in this volume present the state of the art in a variety of areas of discrete probability, including random walks on finite and infinite graphs, random trees, renewal sequences, Stein's method for normal approximation and Kohonen-type self-organizing maps. This volume also focuses on discrete probability and its connections with the theory of algorithms. Classical topics in discrete mathematics are represented as are expositions that condense and make readable some recent work on Markov chains, potential theory and the second moment method. This volume is suitable for mathematicians and students.

It is gratifying that this textbook is still sufficiently popular to warrant a third edition. I have used the opportunity to improve and enlarge the book. When the second edition was prepared, only two pages on algebraic geometry codes were added. These have now been removed and replaced by a relatively long chapter on this subject. Although it is still only an introduction, the chapter requires more mathematical background of the reader than the remainder of this book. One of the very interesting recent developments concerns binary codes defined by using codes over the alphabet 7l.4 There is so much interest in this area that a chapter on the essentials was added. Knowledge of this chapter will allow the reader to study recent literature on 7l. -codes. 4 Furthermore, some material has been added that appeared in my Springer Lec ture Notes 201, but was not included in earlier editions of this book, e. g. Generalized Reed-Solomon Codes and Generalized Reed-Muller Codes. In Chapter 2, a section on "Coding Gain" ( the engineer's justification for using error-correcting codes) was added. For the author, preparing this third edition was a most welcome return to mathematics after seven years of administration. For valuable discussions on the new material, I thank C.P.l.M.Baggen, I. M.Duursma, H.D.L.Hollmann, H. C. A. van Tilborg, and R. M. Wilson. A special word of thanks to R. A. Pellikaan for his assistance with Chapter 10."

"Data Correcting Approaches in Combinatorial Optimization" focuses on algorithmic applications of thewell known polynomially solvable special cases of computationally intractable problems. The purpose of this text is to design practically efficient algorithms for solving wide classes of combinatorial optimization problems. Researches, students and engineers will benefit from new bounds and branching rules in development efficient branch-and-bound type computational algorithms. This book examines applications for solving the Traveling Salesman Problem and its variations, Maximum Weight Independent Set Problem, Different Classes of Allocation and Cluster Analysis as well as some classes of Scheduling Problems. Data Correcting Algorithms in Combinatorial Optimization introduces the data correcting approach to algorithms which provide an answer to the following questions: how to construct a bound to the original intractable problem and findwhich element of the corrected instance one should branch such that the total size of search tree will be minimized. The PC time needed for solving intractable problems will be adjusted with the requirements for solving real world problems. "

Transportation problems belong to the domains mathematical program ming and operations research. Transportation models are widely applied in various fields. Numerous concrete problems (for example, assignment and distribution problems, maximum-flow problem, etc. ) are formulated as trans portation problems. Some efficient methods have been developed for solving transportation problems of various types. This monograph is devoted to transportation problems with minimax cri teria. The classical (linear) transportation problem was posed several decades ago. In this problem, supply and demand points are given, and it is required to minimize the transportation cost. This statement paved the way for numerous extensions and generalizations. In contrast to the original statement of the problem, we consider a min imax rather than a minimum criterion. In particular, a matrix with the minimal largest element is sought in the class of nonnegative matrices with given sums of row and column elements. In this case, the idea behind the minimax criterion can be interpreted as follows. Suppose that the shipment time from a supply point to a demand point is proportional to the amount to be shipped. Then, the minimax is the minimal time required to transport the total amount. It is a common situation that the decision maker does not know the tariff coefficients. In other situations, they do not have any meaning at all, and neither do nonlinear tariff objective functions. In such cases, the minimax interpretation leads to an effective solution.

The author, who died in 1984, is well-known both as a person and through his research in mathematical logic and theoretical computer science. In the first part of the book he presents the new classical theory of finite automata as unary algebras which he himself invented about 30 years ago. Many results, like his work on structure lattices or his characterization of regular sets by generalized regular rules, are unknown to a wider audience. In the second part of the book he extends the theory to general (non-unary, many-sorted) algebras, term rewriting systems, tree automata, and pushdown automata. Essentially Buchi worked independent of other rersearch, following a novel and stimulating approach. He aimed for a mathematical theory of terms, but could not finish the book. Many of the results are known by now, but to work further along this line presents a challenging research program on the borderline between universal algebra, term rewriting systems, and automata theory. For the whole book and again within each chapter the author starts at an elementary level, giving careful explanations and numerous examples and exercises, and then leads up to the research level. In this way he covers the basic theory as well as many nonstandard subjects. Thus the book serves as a textbook for both the beginner and the advances student, and also as a rich source for the expert.

Sphere Packings is one of the most attractive and challenging subjects in mathematics. Almost 4 centuries ago, Kepler studied the densities of sphere packings and made his famous conjecture. In the course of centuries, many exciting results have been obtained, ingenious methods created, related challenging problems proposed, and many surprising connections with othe subjects found. Thus, though some of its original problems are still open, sphere packings has been developed into an important discipline. This book tries to give a full account of this fascinating subject, especially its local aspects, discrete aspects and its proof methods.

A study of topology and geometry, beginning with a comprehensible account of the extraordinary and rather mysterious impact of mathematical physics, and especially gauge theory, on the study of the geometry and topology of manifolds. The focus of the book is the Yang-Mills-Higgs field and some considerable effort is expended to make clear its origin and significance in physics. Much of the mathematics developed here to study these fields is standard, but the treatment always keeps one eye on the physics and sacrifices generality in favor of clarity. The author brings readers up the level of physics and mathematics needed to conclude with a brief discussion of the Seiberg-Witten invariants. A large number of exercises are included to encourage active participation on the part of the reader.

These sequences exhibit some surprising properties that make them a fascinating subject for research in combinatorial analysis. This 1995 book on the subject by two of its leading researchers will be an important resource for students and professionals in combinatorics, computational geometry and related fields.

Excellent authors, such as Lovasz, one of the five best combinatorialists in the world; Thematic linking that makes it a coherent collection; Will appeal to a variety of communities, such as mathematics, computer science and operations research

This IMA Volume in Mathematics and its Applications Coding Theory and Design Theory Part II: Design Theory is based on the proceedings of a workshop which was an integral part of the 1987-88 IMA program on APPLIED COMBINATORICS. We are grateful to the Scientific Committee: Victor Klee (Chairman), Daniel Kleitman, Dijen Ray-Chaudhuri and Dennis Stanton for planning and implementing an exciting and stimulating year long program. We especially thank the Workshop Organizer, Dijen Ray-Chaudhuri, for organizing a workshop which brought together many of the major figures in a variety of research fields in which coding theory and design theory are used. A vner Friedman Willard Miller, Jr. PREFACE Coding Theory and Design Theory are areas of Combinatorics which found rich applications of algebraic structures. Combinatorial designs are generalizations of finite geometries. Probably, the history of Design Theory begins with the 1847 pa per of Reverand T. P. Kirkman "On a problem of Combinatorics," Cambridge and Dublin Math. Journal. The great Statistician R. A. Fisher reinvented the concept of combinatorial 2-design in the twentieth century. Extensive application of alge braic structures for construction of 2-designs (balanced incomplete block designs) can be found in RC. Bose's 1939 Annals of Eugenics paper, "On the construction of balanced incomplete block designs." Coding Theory and Design Theory are closely interconnected. Hamming codes can be found (in disguise) in RC. Bose's 1947 Sankhya paper "Mathematical theory of the symmetrical factorial designs.""

This book constitutes the refereed proceedings of the 9th International Conference on Combinatorics on Words, WORDS 2013, held in Turku, Finland, in September 2013 under the auspices of the EATCS. The 20 revised full papers presented were carefully reviewed and selected from 43 initial submissions. The central topic of the conference is combinatorics on words (i.e. the study of finite and infinite sequence of symbols) from varying points of view, including their combinatorial, algebraic and algorithmic aspects, as well as their applications.

The papers presented here describe research to improve the general understanding of the application of SAMR to practical problems, to identify issues critical to efficient and effective implementation on high performance computers and to stimulate the development of a community code repository for software including benchmarks to assist in the evaluation of software and compiler technologies. The ten chapters have been divided into two parts reflecting two major issues in the topic: programming complexity of SAMR algorithms and the applicability and numerical challenges of SAMR methods.

xiv aggregates: this touches on the very nature of things. The concept of statistical symmetry which Loeb develops is particularly important, it emphasizes the limitations in seemingly random aggregates and for permits general statements of which the crystallographer's sym metries are only special cases. The reductionist and holistic approaches to the world have been at war with each other since the times of the Greek philosophers and before. In nature, parts clearly do fit together into real structures, and the parts are affected by their environment. The problem is one of understanding. The mystery that remains lies largely in the nature of structural hierarchy, for the human mind can examine nature on many different scales sequentially but not simultaneously. Arthur Loeb's monograph is a fundamental one, but one can sense a devel opment from the relations between his zero-and three-dimensional cells to the far more complex world of organisms and concepts. It is structure that makes the difference between a cornfield and a cake, between an aggregate of cells and a human being, between a random group of human beings and a society. We can perceive anything only when we perceive its structure, and we think by structural analogy and comparison. Several books have been published showing the beauty of form in nature. This one has the beauty of a work of art, but it grows out of rigorous mathematics and from the simplest of bases-dimensional ity, extent and valency."

Graph Theory is a part of discrete mathematics characterized by the fact of an extremely rapid development during the last 10 years. The number of graph theoretical paper as well as the number of graph theorists increase very strongly. The main purpose of this book is to show the reader the variety of graph theoretical methods and the relation to combinatorics and to give him a survey on a lot of new results, special methods, and interesting informations. This book, which grew out of contributions given by about 130 authors in honour to the 70th birthday of Gerhard Ringel, one of the pioneers in graph theory, is meant to serve as a source of open problems, reference and guide to the extensive literature and as stimulant to further research on graph theory and combinatorics.

One of the important areas of contemporary combinatorics is Ramsey theory. Ramsey theory is basically the study of structure preserved under partitions. The general philosophy is reflected by its interdisciplinary character. The ideas of Ramsey theory are shared by logicians, set theorists and combinatorists, and have been successfully applied in other branches of mathematics. The whole subject is quickly developing and has some new and unexpected applications in areas as remote as functional analysis and theoretical computer science. This book is a homogeneous collection of research and survey articles by leading specialists. It surveys recent activity in this diverse subject and brings the reader up to the boundary of present knowledge. It covers virtually all main approaches to the subject and suggests various problems for individual research.

This IMA Volume in Mathematics and its Applications Applications of Combinatorics and Graph Theory to the Biological and Social Sciences is based on the proceedings of a workshop which was an integral part of the 1987-88 IMA program on APPLIED COMBINATORICS. We are grateful to the Scientific Committee: Victor Klee (Chairman), Daniel Kleitman, Dijen Ray-Chaudhuri and Dennis Stanton for planning and implementing an exciting and stimulating year long program. We especially thank the Workshop Organizers, Joel Cohen and Fred Roberts, for organizing a workshop which brought together many of the major figures in a variety of research fields connected with the application of combinatorial ideas to the social and biological sciences. A vner Friedman Willard Miller APPLICATIONS OF COMBINATORICS AND GRAPH THEORY TO THE BIOLOGICAL AND SOCIAL SCIENCES: SEVEN FUNDAMENTAL IDEAS FRED S. RoBERTS* Abstract. To set the stage for the other papers in this volume, seven fundamental concepts which arise in the applications of combinatorics and graph theory in the biological and social sciences are described. These ideas are: RNA chains as "words" in a 4 letter alphabet; interval graphs; competition graphs or niche overlap graphs; qualitative stability; balanced signed graphs; social welfare functions; and semiorders. For each idea, some basic results are presented, some recent results are given, and some open problems are mentioned."

This book was first published in 2003. Combinatorica, an extension to the popular computer algebra system Mathematica (R), is the most comprehensive software available for teaching and research applications of discrete mathematics, particularly combinatorics and graph theory. This book is the definitive reference/user's guide to Combinatorica, with examples of all 450 Combinatorica functions in action, along with the associated mathematical and algorithmic theory. The authors cover classical and advanced topics on the most important combinatorial objects: permutations, subsets, partitions, and Young tableaux, as well as all important areas of graph theory: graph construction operations, invariants, embeddings, and algorithmic graph theory. In addition to being a research tool, Combinatorica makes discrete mathematics accessible in new and exciting ways to a wide variety of people, by encouraging computational experimentation and visualization. The book contains no formal proofs, but enough discussion to understand and appreciate all the algorithms and theorems it contains.