Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Preliminaries

Abstract
It seems convenient to list at the outset a few items that will be used throughout the book.
Martin Aigner

Chapter I. Mappings

Abstract
The starting point for all our considerations is the following: We are given two sets, usually denoted by N and R, and a mapping f:NR satisfying certain conditions. The triple (N, R, f) is called a morphism. Our program is to arrange mappings into classes, and then to count and order the resulting classes of mappings.
Martin Aigner

Chapter II. Lattices

Abstract
After having introduced in chapter I the main classes of mappings, let us now study in some depth the various types of lattices encountered there. It seems appropriate to proceed from the most special class of distributive lattices to the more general types, modular, semimodular, and geometric lattices, particularly in view of the fact that each of the three characterizations we shall derive for distributive lattices will lead directly to an important branch of combinatorial theory: matroids and combinatorial geometries to be discussed in chapters VI and VII, the inversion calculus (chapters III and IV), and transversal theory (chapter VIII).
Martin Aigner

Chapter III. Counting Functions

Abstract
Consider the family of n-subsets of a set R or the family of r-partitions of a set N. In chapter I, these families were viewed as special patterns whereas in chapter II they appeared as levels of certain lattices. In this chapter we want to count patterns and lattice levels starting from table 1.13 on the one hand and the fundamental examples of section II.4 on the other. In accordance with the set-up of the book we shall concentrate more on deriving general counting principles rather than on supplying a large set of recursion and inversion formulae for well-known coefficients such as the binomial coefficients or various partition numbers. For a good collection of the latter the reader is referred to Riordan [1, 2] or to Knuth [1. vol. 1].
Martin Aigner

Chapter IV. Incidence Functions

Abstract
After having computed the level numbers and the total number of elements of some important lattices in the last chapter we now consider counting functions and inversion formulae in an arbitrary poset. Our method of study will be to associate with the poset P an algebraic object called the incidence algebra A(P), and to investigate its structure and subobjects.
Martin Aigner

Chapter V. Generating Functions

Abstract
In the course of our investigation of counting problems we have encountered many functions c = c(k) depending on an integral parameter k = 0,1,2,… Most of the time the parameter had something to do with the type classification of the underlying incidence algebra. Our goal is now to find the solution c(0), c(1), c(2),… in a closed form instead of having to evaluate each term c(k) individually. To accomplish this we regard c(k) = c k as coefficient of a formal power series and develop methods to compute this series, called the generating function for the coefficients c k .
Martin Aigner

Chapter VI. Matroids: Introduction

Abstract
Matroids were introduced in the early 1930’s in an attempt to axiomatize and generalize basic notions in linear algebra such as dependence, basis and span. The importance of matroids came to be appreciated with the discovery of new classes of matroids so that today we may rightly consider them as a unifying concept for a large part of combinatorics opening up basic combinatorial questions to algebraic ideas and methods. One of these fields is graph theory; in fact, it was precisely this correspondence between concepts in linear algebra and concepts in graph theory which set the theory of matroids on its way. Since then, other branches of combinatorics such as transversal theory, incidence structures and combinatorial lattice theory have been brought successfully into the realm of matroid theory. Indeed, it is this exchange of ideas from various fields which is one of the most gratifying aspects of matroid theory and also one measure of its success.
Martin Aigner

Chapter VII. Matroids: Further Theory

Abstract
After our discussion of the basics of matroid theory in the previous chapter, we are now going to study in detail the most important classes of matroids: Linear matroids, binary and regular matroids, graphic and transversal matroids. The emphasis lies here on the characterization of these matroids and on applications to concrete combinatorial problems.
Martin Aigner

Chapter VIII. Combinatorial Order Theory

Abstract
Under the general term “combinatorial order theory” we want to collect some results on posets by concentrating less on the structure of posets than on properties present in any poset, such as chains, antichains, matchings, etc. Typical problems to be considered are the determination of the minimal number of chains into which a finite poset can be decomposed or the existence of a matching between the points and copoints of a ranked poset. In fact, the importance of this branch of combinatorial mathematics derives to a large extent from the fact that most of the main results are existence theorems supplementing the many counting results established in chapters III to V. To testify to the broad range of applications, we have included a variety of examples from different sources (graphs, networks, 0,1-matrices, etc.). Each of the sections is headed by a basic theorem after which we study variations of the main theorem, applications, and the mutual dependence with other results.
Martin Aigner

Backmatter

Weitere Informationen