Skip to main content
main-content

Über dieses Buch

Written by one of the foremost experts in the field, Algebraic Combinatorics is a unique undergraduate textbook that will prepare the next generation of pure and applied mathematicians. The combination of the author’s extensive knowledge of combinatorics and classical and practical tools from algebra will inspire motivated students to delve deeply into the fascinating interplay between algebra and combinatorics. Readers will be able to apply their newfound knowledge to mathematical, engineering, and business models.

The text is primarily intended for use in a one-semester advanced undergraduate course in algebraic combinatorics, enumerative combinatorics, or graph theory. Prerequisites include a basic knowledge of linear algebra over a field, existence of finite fields, and group theory. The topics in each chapter build on one another and include extensive problem sets as well as hints to selected exercises. Key topics include walks on graphs, cubes and the Radon transform, the Matrix–Tree Theorem, and the Sperner property. There are also three appendices on purely enumerative aspects of combinatorics related to the chapter material: the RSK algorithm, plane partitions, and the enumeration of labeled trees.

Richard Stanley is currently professor of Applied Mathematics at the Massachusetts Institute of Technology. Stanley has received several awards including the George Polya Prize in applied combinatorics, the Guggenheim Fellowship, and the Leroy P. Steele Prize for mathematical exposition. Also by the author: Combinatorics and Commutative Algebra, Second Edition, © Birkhauser.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Walks in Graphs

Given a finite set S and integer k≥0, let \(\binom{S}{k}\) denote the set of k-element subsets of S. A multiset may be regarded, somewhat informally, as a set with repeated elements, such as {1,1,3,4,4,4,6,}. We are only concerned with how many times each element occurs and not on any ordering of the elements. Thus for instance {2,1,2,4,1,2} and {1,1,2,2,2,4} are the same multiset: they each contain two 1’s, three 2’s, and one 4 (and no other elements).
Richard P. Stanley

Chapter 2. Cubes and the Radon Transform

Let us now consider a more interesting example of a graph G, one whose eigenvalues have come up in a variety of applications. Let \(\mathbb{Z}_{2}\) denote the cyclic group of order 2, with elements 0 and 1 and group operation being addition modulo 2.
Richard P. Stanley

Chapter 3. Random Walks

Let G be a finite graph. We consider a random walk on the vertices of G of the following type. Start at a vertex u. (The vertex u could be chosen randomly according to some probability distribution or could be specified in advance.) Among all the edges incident to u, choose one uniformly at random (i.e., if there are k edges incident to u, then each of these edges is chosen with probability 1∕k). Travel to the vertex v at the other end of the chosen edge and continue as before from v. Readers with some familiarity with probability theory will recognize this random walk as a special case of a finite-state Markov chain. Many interesting questions may be asked about such walks; the basic one is to determine the probability of being at a given vertex after a given number of steps.
Richard P. Stanley

Chapter 4. The Sperner Property

In this chapter we consider a surprising application of certain adjacency matrices to some problems in extremal set theory. An important role will also be played by finite groups in Chap.5, which is a continuation of the present chapter. In general, extremal set theory is concerned with finding (or estimating) the most or least number of sets satisfying given set-theoretic or combinatorial conditions. For example, a typical easy problem in extremal set theory is the following: what is the most number of subsets of an n-element set with the property that any two of them intersect? (Can you solve this problem?) The problems to be considered here are most conveniently formulated in terms of partially ordered sets or posets for short. Thus we begin with discussing some basic notions concerning posets.
Richard P. Stanley

Chapter 5. Group Actions on Boolean Algebras

Let us begin by reviewing some facts from group theory. Suppose that X is an n-element set and that G is a group. We say that Gacts on the set X if for every element π of G we associate a permutation (also denoted π) of X, such that for all xX and π,σG we have
$$\displaystyle{\pi (\sigma (x)) = (\pi \sigma )(x).}$$
Thus [why?] an action of G on X is the same as a homomorphism
Richard P. Stanley

Chapter 6. Young Diagrams and q-Binomial Coefficients

A partitionλ of an integer n ≥ 0 is a sequence \(\lambda = (\lambda _{1},\lambda _{2},\ldots )\) of integers λ i ≥ 0 satisfying λ 1λ 2 ≥ ⋯ and i ≥ 1 λ i = n.
Richard P. Stanley

Chapter 7. Enumeration Under Group Action

In Chaps. 5 and 6 we considered the quotient poset B n G, where G is a subgroup of the symmetric group \(\mathfrak{S}_{n}\). If p i is the number of elements of rank i of this poset, then the sequence p 0, p 1, , p n is rank-symmetric and rank-unimodal.
Richard P. Stanley

Chapter 8. A Glimpse of Young Tableaux

We defined in Chap. 6 Young’s lattice Y, the poset of all partitions of all nonnegative integers, ordered by containment of their Young diagrams.
Richard P. Stanley

Chapter 9. The Matrix-Tree Theorem

The Matrix-Tree Theorem is a formula for the number of spanning trees of a graph in terms of the determinant of a certain matrix. We begin with the necessary graph-theoretical background. Let G be a finite graph, allowing multiple edges but not loops. (Loops could be allowed, but they turn out to be completely irrelevant.
Richard P. Stanley

Chapter 10. Eulerian Digraphs and Oriented Trees

A famous problem which goes back to Euler asks for what graphs G is there a closed walk which uses every edge exactly once. (There is also a version for non-closed walks.) Such a walk is called an Eulerian tour (also known as an Eulerian cycle). A graph which has an Eulerian tour is called an Eulerian graph. Euler’s famous theorem (the first real theorem of graph theory) states that a graph G without isolated vertices (which clearly would be irrelevant) is Eulerian if and only if it is connected and every vertex has even degree. Here we will be concerned with the analogous theorem for directed graphs. We want to know not just whether an Eulerian tour exists, but also how many there are. We will prove an elegant determinantal formula for this number closely related to the Matrix-Tree Theorem. For the case of undirected graphs no analogous formula is known, explaining why we consider only the directed case.
Richard P. Stanley

Chapter 11. Cycles, Bonds, and Electrical Networks

In this chapter we will deal with some interesting linear algebra related to the structure of a directed graph. Let D=(V,E) be a digraph. A function \(f : E \rightarrow \mathbb{R}\) is called a circulation if for every vertex vV we have
$$\displaystyle{ \sum _{{ e\in E \atop \mathrm{init}(e)=v} }f(e) =\sum _{{ e\in E \atop \mathrm{fin}(e)=v} }f(e). }$$
(11.1)
Thus if we think of the edges as pipes and f as measuring the flow (quantity per unit of time) of some commodity (such as oil) through the pipes in the specified direction (so that a negative value of f(e) means a flow of|f(e)|in the direction opposite the direction of e), then (11.1) simply says that the amount flowing into each vertex equals the amount flowing out. In other words, the flow is conservative. The figure below illustrates a circulation in a digraph D.
Richard P. Stanley

Chapter 12. Miscellaneous Gems of Algebraic Combinatorics

An evil warden is in charge of 100 prisoners (all with different names). He puts a row of 100 boxes in a room. Inside each box is the name of a different prisoner. The prisoners enter the room one at a time. Each prisoner must open 50 of the boxes, one at a time. If any of the prisoners does not see his or her own name, then they are all killed. The prisoners may have a discussion before the first prisoner enters the room with the boxes, but after that there is no further communication. A prisoner may not leave a message of any kind for another prisoner. In particular, all the boxes are shut once a prisoner leaves the room. If all the prisoners choose 50 boxes at random, then each has a success probability of 1/2, so the probability that they are not killed is 2−100, not such good odds. Is there a strategy that will increase the chances of success? What is the best strategy?
Richard P. Stanley

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise