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

x

X

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

v

V

we have

11.1

$$\displaystyle{ \sum _{{ e\in E \atop \mathrm{init}(e)=v} }f(e) =\sum _{{ e\in E \atop \mathrm{fin}(e)=v} }f(e). }$$

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

Neuer Inhalt

BranchenIndex Online

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

Whitepaper

- ANZEIGE -

Product Lifecycle Management im Konzernumfeld – Herausforderungen, Lösungsansätze und Handlungsempfehlungen

Für produzierende Unternehmen hat sich Product Lifecycle Management in den letzten Jahrzehnten in wachsendem Maße zu einem strategisch wichtigen Ansatz entwickelt. Forciert durch steigende Effektivitäts- und Effizienzanforderungen stellen viele Unternehmen ihre Product Lifecycle Management-Prozesse und -Informationssysteme auf den Prüfstand. Der vorliegende Beitrag beschreibt entlang eines etablierten Analyseframeworks Herausforderungen und Lösungsansätze im Product Lifecycle Management im Konzernumfeld.
Jetzt gratis downloaden!

Bildnachweise