Global Methods for Combinatorial Isoperimetric Problems

The main theme of the book is the edge-isoperimetric problem (EIP), which is to find a set of vertices of a given size and with the minimum number of edges leaving the set in a given graph. The first chapter presents an elementary (though not easy) solution of EIP for hypercube and an application to the wirelength problem. The next chapter describes a reduction to the problem of finding a minimal path in a certain network. This brings us to global methods mentioned in the title. A morphism between networks (a pathmorphism) is defined and shown to preserve the minimum path. In the next chapter, two basic constructions of a pathmorphism (stabilization and compression) are presented. This uses a symmetry or the product decomposition of the graph and in many instances leads to a tremendous simplification of the problem. In particular, the EIP for the hypercube becomes trivial. The fourth chapter repeats the whole process for the vertex-isoperimetric problem, and elements of the Coxeter theory of groups are presented and used to facilitate stabilization in the fifth chapter.
In the second half, the theory is extended in various ways. Two chapters deal with hypergraphs and with infinite graphs. A further two chapters are devoted to the maximum weight ideal problem. This leads to the Ahlswede-Cai theorem and to the Bezrukov-Das-Elsässer theorem (EIP for powers of the Petersen graph). In the last chapter, a continuous approximation of EIP is described; in particular, a theorem by Bollobás and Leader is presented. Besides presentation of the theory, the book contains well-chosen exercises to help the reader's comprehension and insightful comments including the author's biographical remarks on developing this area of combinatorics. No prior knowledge is assumed. The book may be used for a semester graduate course. It is an illustrative and innovative application of the notion of a morphism to concrete combinatorial problems and as such, it may be recommended to a general audience. It is a real pleasure to read the book, because it offers to the reader not only a description of the theory but also an explanation on how the theory was developed.

Book details




User login