This volume contains the accounts of papers delivered at the Nato Advanced Study Institute on Finite and Infinite Combinatorics in Sets and Logic held at the Banff Centre, Alberta, Canada from April 21 to May 4, 1991. As the title suggests the meeting brought together workers interested in the interplay between finite and infinite combinatorics, set theory, graph theory and logic. It used to be that infinite set theory, finite combinatorics and logic could be viewed as quite separate and independent subjects. But more and more those disciplines grow together and become interdependent of each other with ever more problems and results appearing which concern all of those disciplines. I appreciate the financial support which was provided by the N. A. T. O. Advanced Study Institute programme, the Natural Sciences and Engineering Research Council of Canada and the Department of Mathematics and Statistics of the University of Calgary. 11l'te meeting on Finite and Infinite Combinatorics in Sets and Logic followed two other meetings on discrete mathematics held in Banff, the Symposium on Ordered Sets in 1981 and the Symposium on Graphs and Order in 1984. The growing inter-relation between the different areas in discrete mathematics is maybe best illustrated by the fact that many of the participants who were present at the previous meetings also attended this meeting on Finite and Infinite Combinatorics in Sets and Logic.
AMS-ASL Joint Special Session, January 5-8, 2009, Washington, DC
Author: Martin Grohe
Publisher: American Mathematical Soc.
This volume contains the proceedings of the AMS-ASL Special Session on Model Theoretic Methods in Finite Combinatorics, held January 5-8, 2009, in Washington, DC. Over the last 20 years, various new connections between model theory and finite combinatorics emerged. The best known of these are in the area of 0-1 laws, but in recent years other very promising interactions between model theory and combinatorics have been developed in areas such as extremal combinatorics and graph limits, graph polynomials, homomorphism functions and related counting functions, and discrete algorithms, touching the boundaries of computer science and statistical physics. This volume highlights some of the main results, techniques, and research directions of the area. Topics covered in this volume include recent developments on 0-1 laws and their variations, counting functions defined by homomorphisms and graph polynomials and their relation to logic, recurrences and spectra, the logical complexity of graphs, algorithmic meta theorems based on logic, universal and homogeneous structures, and logical aspects of Ramsey theory.
Numbers imitate space, which is of such a di?erent nature —Blaise Pascal It is fair to date the study of the foundation of mathematics back to the ancient Greeks. The urge to understand and systematize the mathematics of the time led Euclid to postulate axioms in an early attempt to put geometry on a ?rm footing. With roots in the Elements, the distinctive methodology of mathematics has become proof. Inevitably two questions arise: What are proofs? and What assumptions are proofs based on? The ?rst question, traditionally an internal question of the ?eld of logic, was also wrestled with in antiquity. Aristotle gave his famous syllogistic s- tems, and the Stoics had a nascent propositional logic. This study continued with ?ts and starts, through Boethius, the Arabs and the medieval logicians in Paris and London. The early germs of logic emerged in the context of philosophy and theology. The development of analytic geometry, as exempli?ed by Descartes, ill- tratedoneofthedi?cultiesinherentinfoundingmathematics. Itisclassically phrased as the question ofhow one reconciles the arithmetic with the geom- ric. Arenumbers onetypeofthingand geometricobjectsanother? Whatare the relationships between these two types of objects? How can they interact? Discovery of new types of mathematical objects, such as imaginary numbers and, much later, formal objects such as free groups and formal power series make the problem of ?nding a common playing ?eld for all of mathematics importunate. Several pressures made foundational issues urgent in the 19th century.
Set theory is an autonomous and sophisticated field of mathematics that is extremely successful at analyzing mathematical propositions and gauging their consistency strength. It is as a field of mathematics that both proceeds with its own internal questions and is capable of contextualizing over a broad range, which makes set theory an intriguing and highly distinctive subject. This handbook covers the rich history of scientific turning points in set theory, providing fresh insights and points of view. Written by leading researchers in the field, both this volume and the Handbook as a whole are definitive reference tools for senior undergraduates, graduate students and researchers in mathematics, the history of philosophy, and any discipline such as computer science, cognitive psychology, and artificial intelligence, for whom the historical background of his or her work is a salient consideration Serves as a singular contribution to the intellectual history of the 20th century Contains the latest scholarly discoveries and interpretative insights
In 1992, when Paul Erdos was awarded a Doctor Honoris Causa by Charles University in Prague, a small conference was held, bringing together a distin guished group of researchers with interests spanning a variety of fields related to Erdos' own work. At that gathering, the idea occurred to several of us that it might be quite appropriate at this point in Erdos' career to solicit a col lection of articles illustrating various aspects of Erdos' mathematical life and work. The response to our solicitation was immediate and overwhelming, and these volumes are the result. Regarding the organization, we found it convenient to arrange the papers into six chapters, each mirroring Erdos' holistic approach to mathematics. Our goal was not merely a (random) collection of papers but rather a thor oughly edited volume composed in large part by articles explicitly solicited to illustrate interesting aspects of Erdos and his life and work. Each chap ter includes an introduction which often presents a sample of related Erdos' problems "in his own words". All these (sometimes lengthy) introductions were written jointly by editors. We wish to thank the nearly 70 contributors for their outstanding efforts (and their patience). In particular, we are grateful to Bela Bollobas for his extensive documentation of Paul Erdos' early years and mathematical high points (in the first part of this volume); our other authors are acknowledged in their respective chapters. We also want to thank A. Bondy, G. Hahn, I.
This book is a tribute to Paul Erdos, the wandering mathematician once described as the "prince of problem solvers and the absolute monarch of problem posers." It examines the legacy of open problems he left to the world after his death in 1996.
This book applies model theoretic methods to the study of certain finite permutation groups, the automorphism groups of structures for a fixed finite language with a bounded number of orbits on 4-tuples. Primitive permutation groups of this type have been classified by Kantor, Liebeck, and Macpherson, using the classification of the finite simple groups. Building on this work, Gregory Cherlin and Ehud Hrushovski here treat the general case by developing analogs of the model theoretic methods of geometric stability theory. The work lies at the juncture of permutation group theory, model theory, classical geometries, and combinatorics. The principal results are finite theorems, an associated analysis of computational issues, and an "intrinsic" characterization of the permutation groups (or finite structures) under consideration. The main finiteness theorem shows that the structures under consideration fall naturally into finitely many families, with each family parametrized by finitely many numerical invariants (dimensions of associated coordinating geometries). The authors provide a case study in the extension of methods of stable model theory to a nonstable context, related to work on Shelah's "simple theories." They also generalize Lachlan's results on stable homogeneous structures for finite relational languages, solving problems of effectivity left open by that case. Their methods involve the analysis of groups interpretable in these structures, an analog of Zilber's envelopes, and the combinatorics of the underlying geometries. Taking geometric stability theory into new territory, this book is for mathematicians interested in model theory and group theory.
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.
This book has arisen from a colloquium held at St. John's College, Cambridge, in July 1989, which brought together most of today's leading experts in the field of infinite graph theory and combinatorics. This was the first such meeting ever held, and its aim was to assess the state of the art in the discipline, to consider its links with other parts of mathematics, and to discuss possible directions for future development. This volume reflects the Cambridge meeting in both level and scope. It contains research papers as well as expository surveys of particular areas. Together they offer a comprehensive portrait of infinite graph theory and combinatorics, which should be particularly attractive to anyone new to the discipline.