nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Algebraic Combinatorics

Walks, Trees, Tableaux, and More

verfasst von: Richard P. Stanley

Verlag: Springer International Publishing

Buchreihe : Undergraduate Texts in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Ü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 understanding to mathematical, engineering, and business models. Prerequisites include a basic knowledge of linear algebra over a field, existence of finite fields, and rudiments of 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, de Bruijn sequences, the Erdős–Moser conjecture, electrical networks, the Sperner property, shellability of simplicial complexes and face rings. 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.

The new edition contains a bit more content than intended for a one-semester advanced undergraduate course in algebraic combinatorics, enumerative combinatorics, or graph theory. Instructors may pick and choose chapters/sections for course inclusion and students can immerse themselves in exploring additional gems once the course has ended. A chapter on combinatorial commutative algebra (Chapter 12) is the heart of added material in this new edition. The author gives substantial application without requisites needed for algebraic topology and homological algebra. A sprinkling of additional exercises and a new section (13.8) involving commutative algebra, have been added.

From reviews of the first edition:

“This gentle book provides the perfect stepping-stone up. The various chapters treat diverse topics … . Stanley’s emphasis on ‘gems’ unites all this —he chooses his material to excite students and draw them into further study. … Summing Up: Highly recommended. Upper-division undergraduates and above.”

—D. V. Feldman, Choice, Vol. 51(8), April, 2014

Inhaltsverzeichnis

Frontmatter

Chapter 1. Walks in Graphs

Abstract

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, 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

Abstract

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

Abstract

Let G be a finite graph. We assume throughout this chapter that G has at least two vertices and is connected, i.e., there exists a walk between any two vertices of G. 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

Abstract

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 Chapter 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

Abstract

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 G acts 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 $\varphi \colon G\rightarrow \mathfrak {S}_X$, where $\mathfrak {S}_X$ denotes the symmetric group of all permutations of X.

Richard P. Stanley

Chapter 6. Young Diagrams and q-Binomial Coefficients

Abstract

A partition λ of an integer n ≥ 0 is a sequence λ = (λ ₁, λ ₂, … ) of integers λ _i ≥ 0 satisfying λ ₁ ≥ λ ₂ ≥⋯ and ∑_i≥1 λ _i = n. Thus all but finitely many λ _i are equal to 0. Each λ _i > 0 is called a part of λ. We sometimes suppress 0’s from the notation for λ, e.g., (5, 2, 2, 1), (5, 2, 2, 1, 0, 0, 0), and (5, 2, 2, 1, 0, 0, … ) all represent the same partition λ (of 10, with four parts). If λ is a partition of n, then we denote this by λ ⊢ n or |λ| = n.

Richard P. Stanley

Chapter 7. Enumeration Under Group Action

Abstract

In Chapters 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 ₀, p ₁, …, p _n is rank-symmetric and rank-unimodal.

Richard P. Stanley

Chapter 8. A Glimpse of Young Tableaux

Abstract

We defined in Chapter 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

Abstract

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

Abstract

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

Abstract

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\colon E\rightarrow \mathbb {R}$ is called a circulation or flow if for every vertex v ∈ V , we have 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. A Glimpse of Combinatorial Commutative Algebra

Abstract

In this chapter we will discuss a profound connection between commutative rings and some combinatorial properties of simplicial complexes. The deepest and most interesting results in this area require a background in algebraic topology and homological algebra beyond the scope of this book.

Richard P. Stanley

Chapter 13. Miscellaneous Gems of Algebraic Combinatorics

Abstract

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⁻¹⁰⁰, not such good odds. Is there a strategy that will increase the chances of success? What is the best strategy?

Richard P. Stanley

Backmatter

Titel: Algebraic Combinatorics
verfasst von: Richard P. Stanley
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-77173-1
Print ISBN: 978-3-319-77172-4
DOI: https://doi.org/10.1007/978-3-319-77173-1