Thomas Koshy
- Published in print:
- 2008
- Published Online:
- January 2009
- ISBN:
- 9780195334548
- eISBN:
- 9780199868766
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780195334548.003.0010
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter investigates several occurrences of Catalan numbers in the theory of partitioning. Noncrossing partition is explained in detail.
This chapter investigates several occurrences of Catalan numbers in the theory of partitioning. Noncrossing partition is explained in detail.
Pavol Hell and Jaroslav Nešetřil
- Published in print:
- 2004
- Published Online:
- September 2007
- ISBN:
- 9780198528173
- eISBN:
- 9780191713644
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198528173.003.0005
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target ...
More
This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.Less
This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.
Ben Brubaker, Daniel Bump, and Solomon Friedberg
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691150659
- eISBN:
- 9781400838998
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691150659.003.0019
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter reinterprets Statements A and B in a different context, and yet again directly proves that the reinterpreted Statement B implies the reinterpreted Statement A in Theorem 19.10. The ...
More
This chapter reinterprets Statements A and B in a different context, and yet again directly proves that the reinterpreted Statement B implies the reinterpreted Statement A in Theorem 19.10. The p-parts of Weyl group multiple Dirichlet series, with their deformed Weyl denominators, may be expressed as partition functions of exactly solved models in statistical mechanics. The transition to ice-type models represents a subtle shift in emphasis from the crystal basis representation, and suggests the introduction of a new tool, the Yang-Baxter equation. This tool was developed to prove the commutativity of the row transfer matrix for the six-vertex and similar models. This is significant because Statement B can be formulated in terms of the commutativity of two row transfer matrices. This chapter presents an alternate proof of Statement B using the Yang-Baxter equation.Less
This chapter reinterprets Statements A and B in a different context, and yet again directly proves that the reinterpreted Statement B implies the reinterpreted Statement A in Theorem 19.10. The p-parts of Weyl group multiple Dirichlet series, with their deformed Weyl denominators, may be expressed as partition functions of exactly solved models in statistical mechanics. The transition to ice-type models represents a subtle shift in emphasis from the crystal basis representation, and suggests the introduction of a new tool, the Yang-Baxter equation. This tool was developed to prove the commutativity of the row transfer matrix for the six-vertex and similar models. This is significant because Statement B can be formulated in terms of the commutativity of two row transfer matrices. This chapter presents an alternate proof of Statement B using the Yang-Baxter equation.
Ben Brubaker, Daniel Bump, and Solomon Friedberg
- Published in print:
- 2011
- Published Online:
- October 2017
- ISBN:
- 9780691150659
- eISBN:
- 9781400838998
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691150659.003.0020
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics
This chapter describes the properties of Kashiwara's crystal and its role in unipotent p-adic integrations related to Whittaker functions. In many cases, integrations of representation theoretic ...
More
This chapter describes the properties of Kashiwara's crystal and its role in unipotent p-adic integrations related to Whittaker functions. In many cases, integrations of representation theoretic import over the maximal unipotent subgroup of a p-adic group can be replaced by a sum over Kashiwara's crystal. Partly motivated by the crystal description presented in Chapter 2 of this book, this perspective was advocated by Bump and Nakasuji. Later work by McNamara and Kim and Lee extended this philosophy yet further. Indeed, McNamara shows that the computation of the metaplectic Whittaker function is initially given as a sum over Kashiwara's crystal. The chapter considers Kostant's generating function, the character of the quantized enveloping algebra, and its association with Kashiwara's crystal, along with the Kostant partition function and the Weyl character formula.Less
This chapter describes the properties of Kashiwara's crystal and its role in unipotent p-adic integrations related to Whittaker functions. In many cases, integrations of representation theoretic import over the maximal unipotent subgroup of a p-adic group can be replaced by a sum over Kashiwara's crystal. Partly motivated by the crystal description presented in Chapter 2 of this book, this perspective was advocated by Bump and Nakasuji. Later work by McNamara and Kim and Lee extended this philosophy yet further. Indeed, McNamara shows that the computation of the metaplectic Whittaker function is initially given as a sum over Kashiwara's crystal. The chapter considers Kostant's generating function, the character of the quantized enveloping algebra, and its association with Kashiwara's crystal, along with the Kostant partition function and the Weyl character formula.
Robin Wilson and John J. Watkins (eds)
- Published in print:
- 2013
- Published Online:
- September 2013
- ISBN:
- 9780199656592
- eISBN:
- 9780191748059
- Item type:
- book
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199656592.001.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics, History of Mathematics
The history of mathematics is a well-studied and vibrant area of research, with books and scholarly articles published on various aspects of the subject. Yet, the history of combinatorics seems to ...
More
The history of mathematics is a well-studied and vibrant area of research, with books and scholarly articles published on various aspects of the subject. Yet, the history of combinatorics seems to have been largely overlooked. This book goes some way to redress this and serves two main purposes: it constitutes the first book-length survey of the history of combinatorics, and it assembles, for the first time in a single source, researches on the history of combinatorics that would otherwise be inaccessible to the general reader. Individual chapters have been contributed by sixteen experts. The book opens with an introduction to two thousand years of combinatorics. This is followed by seven chapters on early combinatorics, leading from Indian and Chinese writings on permutations to late-Renaissance publications on the arithmetical triangle. The next seven chapters trace the subsequent story, from Euler’s contributions to such wide-ranging topics as partitions, polyhedra, and latin squares to the 20th-century advances in combinatorial set theory, enumeration, and graph theory. The book concludes with some combinatorial reflections.Less
The history of mathematics is a well-studied and vibrant area of research, with books and scholarly articles published on various aspects of the subject. Yet, the history of combinatorics seems to have been largely overlooked. This book goes some way to redress this and serves two main purposes: it constitutes the first book-length survey of the history of combinatorics, and it assembles, for the first time in a single source, researches on the history of combinatorics that would otherwise be inaccessible to the general reader. Individual chapters have been contributed by sixteen experts. The book opens with an introduction to two thousand years of combinatorics. This is followed by seven chapters on early combinatorics, leading from Indian and Chinese writings on permutations to late-Renaissance publications on the arithmetical triangle. The next seven chapters trace the subsequent story, from Euler’s contributions to such wide-ranging topics as partitions, polyhedra, and latin squares to the 20th-century advances in combinatorial set theory, enumeration, and graph theory. The book concludes with some combinatorial reflections.
GEORGE E. ANDREWS
- Published in print:
- 2013
- Published Online:
- September 2013
- ISBN:
- 9780199656592
- eISBN:
- 9780191748059
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199656592.003.0010
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics, History of Mathematics
While Leibniz appears to have been the earliest to consider the partitioning of integers into sums, Euler was the first person to make truly deep discoveries. J. J. Sylvester was the next researcher ...
More
While Leibniz appears to have been the earliest to consider the partitioning of integers into sums, Euler was the first person to make truly deep discoveries. J. J. Sylvester was the next researcher to make major contributions, followed by Fabian Franklin. The 20th century saw an explosion of research with contributions from L. J. Rogers, G. H. Hardy, Percy MacMahon, Srinivasa Ramanujan, and Hans Rademacher.Less
While Leibniz appears to have been the earliest to consider the partitioning of integers into sums, Euler was the first person to make truly deep discoveries. J. J. Sylvester was the next researcher to make major contributions, followed by Fabian Franklin. The 20th century saw an explosion of research with contributions from L. J. Rogers, G. H. Hardy, Percy MacMahon, Srinivasa Ramanujan, and Hans Rademacher.
