Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2013 | Book

Walks in Graphs Read chapter Read first chapter

Algebraic Combinatorics

Walks, Trees, Tableaux, and More

Author: Richard P. Stanley

Publisher: Springer New York

Book Series : Undergraduate Texts in Mathematics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

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,}. 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 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 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
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 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
Abstract
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
Abstract
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
Abstract
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
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 : E \rightarrow \mathbb{R}\) is called a circulation if for every vertex v∈V 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
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−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
Metadata
Title
Algebraic Combinatorics
Author
Richard P. Stanley
Copyright Year
2013
Publisher
Springer New York
Electronic ISBN
978-1-4614-6998-8
Print ISBN
978-1-4614-6997-1
DOI
https://doi.org/10.1007/978-1-4614-6998-8

Premium Partner

    Image Credits