Fact-checked by Grok 2 weeks ago

Algebraic combinatorics

Algebraic combinatorics is a branch of mathematics that employs algebraic structures and methods, such as groups, rings, vector spaces, and generating functions, to investigate and enumerate discrete combinatorial objects like graphs, posets, permutations, and partitions, often revealing deep structural properties and connections to representation theory.^[1]^[2]^[3] This field bridges enumerative combinatorics, which focuses on counting finite sets and their configurations, with algebraic tools that provide proofs of properties like unimodality and symmetry in counting sequences.^[4] Key applications include analyzing group actions on sets to count orbits, as in Pólya enumeration for symmetric colorings, and studying Young tableaux in the context of symmetric group representations.^[4]^[3] Prominent topics encompass symmetric functions, q-analogues for refined counting, the matrix-tree theorem for spanning trees in graphs, and lattice theory for posets like the Boolean or partition lattices.^[1]^[2] Algebraic combinatorics also intersects with geometric methods, such as in the study of Catalan numbers via Dyck paths and noncrossing partitions, highlighting bijections and generating function recurrences.^[1] These techniques have influenced areas like statistical mechanics and computer science, particularly in algorithm design for permutation patterns and parking functions.^[2]^[1]

Overview and Fundamentals

Definition and Scope

Algebraic combinatorics is a branch of mathematics that applies methods from abstract algebra to investigate combinatorial structures and problems, such as counting, enumerating, or classifying discrete objects like graphs, permutations, and partitions, while also employing combinatorial techniques to explore algebraic entities.^[5] This field emphasizes the interplay between algebraic tools—including polynomials, group actions, and vector spaces—and combinatorial inquiries, enabling proofs of existence, structural insights, and asymptotic behaviors that might be inaccessible through purely combinatorial means.^[6] The scope of algebraic combinatorics encompasses the use of generating functions for enumeration, representation theory for analyzing symmetries, and linear algebra for examining properties like eigenvalues in graph spectra, thereby bridging discrete counting with continuous algebraic frameworks.^[5] It differs from pure combinatorics, which relies primarily on bijective proofs and inclusion-exclusion without algebraic machinery, and from algebraic geometry, which centers on polynomial equations defining geometric varieties rather than finite discrete structures.^[5] Within this domain, key problems involve translating combinatorial identities into algebraic relations solvable via ring theory or module decompositions.^[7] Algebraic combinatorics connects to diverse areas, including representation theory through the study of group actions on combinatorial objects, coding theory via error-correcting codes derived from algebraic designs, and physics through partition functions in statistical mechanics that model particle configurations.^[5]^[8]^[9] A representative example is the application of the ring of symmetric polynomials to solve partitioning problems, where these polynomials encode the generating functions for integer partitions, facilitating explicit formulas for their enumeration.^[10]

Historical Development

The foundations of algebraic combinatorics trace back to the early 19th century with Augustin-Louis Cauchy's pioneering work on permutations and the symmetric group. In his 1815 memoir, Cauchy introduced notation and properties for substitutions, laying groundwork for permutation groups, and expanded this in his 1844-1845 publications by systematically developing the theory of conjugate systems of permutations, including results on cycle decompositions and subgroup orders.^[11] Toward the end of the century, Percy MacMahon advanced combinatorial enumeration using generating functions, notably in his 1898 conjecture and subsequent papers on plane partitions, where he employed partition analysis to derive multivariable generating functions for these structures.^[12] In the early 20th century, representation theory of the symmetric group emerged as a key algebraic tool for combinatorics, with Ferdinand Georg Frobenius developing character theory in 1896-1903 and Issai Schur extending it in 1901-1905 to classify irreducible representations via characters, enabling combinatorial interpretations of symmetric group actions.^[13] Alfred Young further contributed around 1900-1903 by introducing Young tableaux as a combinatorial device to construct representations of the symmetric group, bridging invariant theory and enumeration.^[14] By the mid-20th century, these ideas gained combinatorial traction; for instance, Gian-Carlo Rota's 1964 paper on Möbius functions unified poset enumeration with the study of matroids—algebraic structures generalizing linear independence originally introduced by Hassler Whitney in 1935^[15]—revitalizing the field in the 1960s.^[16] The 1970s and 1980s marked rapid growth in algebraic combinatorics, driven by Richard Stanley's enumerative work, including his 1972 thesis on posets and symmetric functions, which systematized bijective proofs and plane partition identities, culminating in his influential 1986 textbook.^[16] Bruce Sagan built on this in the 1980s, applying symmetric functions to permutation statistics and representation theory, as detailed in his 1991 monograph on the symmetric group. A key milestone was the 1939 introduction of association schemes by Raj Chandra Bose and K. R. Nair for analyzing partially balanced incomplete block designs in statistics, later algebraicized for combinatorial designs.^[17] In the 1960s, finite geometries emerged in coding theory through constructions like Bose-Chaudhuri-Hocquenghem codes, leveraging projective spaces over finite fields for error-correcting codes.^[18] Post-2000 developments integrated algebraic combinatorics with algebraic geometry, particularly via quiver representations, where dimension vectors and semi-invariants encode combinatorial data; for example, Derksen and Weyman's 2006 work described faces of weight cones for quiver semi-invariant rings, linking to Littlewood-Richardson coefficients and partition theory.^[19] This era emphasized quiver-based models for cluster algebras and categorification, expanding applications in enumerative invariants.^[20]

Core Algebraic Methods

Symmetric Functions

Symmetric functions are polynomials in an infinite set of variables x_1, x_2, \dots that remain unchanged under any permutation of the variables, and they form a commutative graded ring \Lambda over the integers, where the graded pieces \Lambda_n consist of homogeneous polynomials of degree n.^[21] This ring is freely generated by the power sums and admits several \mathbb{Z}-bases indexed by partitions of n.^[21] Prominent bases include the complete homogeneous symmetric functions h_k, defined as the sum of all monomials of total degree k; the elementary symmetric functions e_k, which sum the products of k distinct variables; the power sum symmetric functions p_k = \sum_i x_i^k; and the Schur functions s_\lambda, indexed by partitions \lambda \vdash n.^[21] These bases are interrelated through invertible transition matrices with integer entries, such as the Kostka matrix relating the h_\lambda to the s_\lambda.^[21] A fundamental set of relations among these bases are the Newton identities, which connect the power sums to the elementary symmetric functions; for instance, for each k \geq 1,

p_k - e_1 p_{k-1} + e_2 p_{k-2} - \cdots + (-1)^{k-1} k e_k = 0.

^[21] Similar identities hold relating the power sums to the complete homogeneous functions.^[21] Combinatorially, the Schur functions admit interpretations as generating functions for semistandard Young tableaux of shape \lambda, where the coefficient of a monomial x_1^{a_1} x_2^{a_2} \cdots counts the number of such tableaux with a_i entries equal to i, and the content is the product of the entries in the tableau.^[21] The transition matrices between bases, such as those expanding Schur functions in terms of power sums, encode combinatorial data like the number of tableaux or other symmetric objects.^[21] In applications, symmetric functions enumerate integer partitions through generating functions like \prod_i (1 - x_i t)^{-1} = \sum_k h_k t^k, which tracks partitions into parts from the variables.^[21] They also arise in the representation theory of the symmetric group S_n, where the Schur functions s_\lambda (for \lambda \vdash n) furnish the Frobenius characteristic of the irreducible representations labeled by \lambda.^[21]

Generating Functions and Species

Generating functions provide a powerful algebraic tool for encoding and manipulating sequences that count combinatorial objects, facilitating the solution of enumeration problems through series manipulations. The ordinary generating function for a sequence (a_n)_{n \geq 0} of non-negative integers is the formal power series A(x) = \sum_{n=0}^\infty a_n x^n, which is particularly suited to unlabeled combinatorial structures where order among identical components does not matter.^[22] In contrast, the exponential generating function A(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!} incorporates the factorial denominator to account for labeled structures, where the n! permutations of labels are indistinguishable in the counting.^[22] This form aligns naturally with operations like differentiation and composition, which correspond to combinatorial constructions such as adding a distinguished element or substituting structures.^[22] A classic example of an exponential generating function arises in the enumeration of permutations: the number of permutations on n labeled elements is n!, so the associated generating function is \sum_{n=0}^\infty n! \frac{x^n}{n!} = \sum_{n=0}^\infty x^n = \frac{1}{1-x} for |x| < 1.^[22] Exponential generating functions excel in labeled settings, such as derangements or matchings, where the n! scaling simplifies recurrences into algebraic equations solvable by methods like partial fractions or singularity analysis.^[22] Combinatorial species, pioneered by André Joyal in the early 1980s, offer a structured, category-theoretic approach to enumeration that unifies generating functions with the combinatorial constructions they represent.^[23] A species F is a contravariant functor from the category of finite sets and bijections to the category of sets, assigning to each finite set U a set F[U] of F-structures on the labels of U, with bijections \sigma: U \to V inducing structure-preserving maps F[\sigma]: F[U] \to F[V].^[24] The exponential generating function of F is then F(x) = \sum_{n \geq 0} |F| \frac{x^n}{n!}, where denotes a canonical n-element set and |F| counts the structures on n labels, naturally extending the labeled enumeration framework.^[24] This perspective, developed in Joyal's foundational work, emphasizes that species encode not just counts but the isomorphism classes and relabeling equivalences inherent in combinatorial objects.^[23] Species support a rich algebra of operations that mirror functional manipulations of their generating functions. The sum F + G defines (F + G)[U] as the disjoint union F[U] \sqcup G[U], corresponding to the addition of generating functions F(x) + G(x) and allowing enumeration of choices between structure types.^[24] The product F \cdot G equips (F \cdot G)[U] with structures that partition U into subsets for F and G, yielding F(x) G(x) and modeling assemblies like sequences or sets of components.^[24] Composition F \circ G substitutes G-structures into the "points" of F-structures, producing F(G(x)) and capturing hierarchical builds such as trees with subtrees.^[24] Additionally, virtual species incorporate signed structures for inclusion-exclusion principles, enabling counts of acyclic or derangement-like objects via differences like F - G.^[24] A cornerstone result in this framework is the cycle index theorem, which adapts Pólya's enumeration theorem to species for counting under group actions. Pólya's theorem, originally formulated in 1937, states that the number of distinct colorings of a set under a group G of permutations is the average of the cycle index polynomial Z(G; x_1, x_2, \dots) = \frac{1}{|G|} \sum_{g \in G} \prod_{k \geq 1} x_k^{c_k(g)}, evaluated at x_k = c for c colors, where c_k(g) is the number of cycles of length k in g.^[22] In the species context, this extends to the cycle index species, providing a generating function for orbit counts under symmetry groups, such as non-isomorphic graph colorings where the automorphism group acts on vertices.^[22] For instance, applying Pólya's theorem to the cyclic group yields formulas for necklace enumerations, a staple in algebraic combinatorics.^[22] These tools find broad applications in algebraic enumeration of complex structures. In tree counting, Joyal's species framework proves Cayley's formula: the number of labeled trees on n vertices is n^{n-2}, derived from the composition equation for rooted trees \mathrm{RTree} = X \cdot \mathrm{Set}(\mathrm{RTree}), whose exponential generating function T(x) = x e^{T(x)} solves via Lagrange inversion to give [x^n] T(x) = n^{n-1}/n!, so the number of rooted labeled trees is n^{n-1}. The number of (unrooted) labeled trees is then n^{n-2}, since each tree admits n rootings.^[23] For graphs, generating functions and Pólya's theorem enumerate unlabeled graphs up to isomorphism, such as the cycle index of the symmetric group for complete graph colorings, reducing vast counts to polynomial evaluations.^[22] Poset enumeration leverages species operations for graded or interval orders, with exponential generating functions capturing antichain decompositions; for example, the generating function for all posets on n labeled elements involves products over linear extensions, though exact closed forms remain challenging and often rely on recursive species equations.

Key Combinatorial Structures

Young Tableaux

A Young tableau is a filling of the boxes of a Young diagram corresponding to a partition \lambda \vdash n with positive integers such that the entries are strictly increasing along each row from left to right and along each column from top to bottom.^[25] A standard Young tableau (SYT) of shape \lambda is one where the entries form a bijection from the boxes to \{1, 2, \dots, n\}, ensuring the increasing conditions hold.^[26] In contrast, a semi-standard Young tableau (SSYT) allows entries from \{1, 2, \dots, k\} for some k, with entries weakly increasing along rows (non-decreasing) but still strictly increasing along columns.^[27] These structures provide bijective encodings that connect integer partitions to lattice paths and algebraic objects in representation theory. The number of standard Young tableaux of shape \lambda \vdash n, denoted f^\lambda, is given by the hook-length formula:

f^\lambda = \frac{n!}{\prod_{(i,j) \in \lambda} h_{(i,j)}},

where h_{(i,j)} is the hook length of the cell at row i, column j, defined as the number of cells to the right of (i,j) plus the number below it, plus one for the cell itself.^[28] For example, consider the partition \lambda = (2,1). The hook lengths are 3 for (1,1), 1 for (1,2), and 1 for (2,1), yielding f^\lambda = 3! / (3 \cdot 1 \cdot 1) = 2. The two standard Young tableaux are:

\begin{array}{cc} 1 & 2 \\ 3 & \end{array} \qquad \begin{array}{cc} 1 & 3 \\ 2 & \end{array}

This formula admits multiple combinatorial proofs, including bijective interpretations via jeu de taquin paths and probabilistic arguments using uniform random SYT generation.^[22] The Robinson–Schensted–Knuth (RSK) correspondence establishes a bijection between nonnegative integer matrices (or generalized permutations) and pairs of semi-standard Young tableaux (P, Q) of the same shape \lambda.^[29] The algorithm proceeds by row insertion: to insert a value x into the insertion tableau P, start in the first row and bump the smallest entry strictly larger than x to the next row, repeating until no bump occurs, then add a new box if necessary; the recording tableau Q tracks the positions of new boxes with increasing labels.^[30] Reverse deletion via jeu de taquin recovers the matrix, ensuring invertibility. Key properties include preservation of the matrix trace as the sum of the main diagonal of P, and for permutation matrices, the shape \lambda_1 equals the length of the longest increasing subsequence.^[29] Combinatorial proofs of these rely on induction over insertion steps, showing that bumping paths form lattice paths avoiding certain configurations. In the context of singular value decomposition, applying RSK to a matrix yields tableaux whose shape encodes the ordered singular values, linking combinatorial growth models to spectral properties.^[31] In applications, the number f^\lambda equals the dimension of the irreducible representation V^\lambda of the symmetric group S_n indexed by \lambda, providing a combinatorial basis for Specht modules via tabloids and Young symmetrizers.^[25] The jeu de taquin operation, introduced by Schützenberger, slides entries in a skew tableau inward to rectify it to a straight shape while preserving the reading word, and enables evacuation by cycling through reverse slides to yield an involution on tableaux with fixed points corresponding to symmetric shapes.^[32] Counts of tableaux under RSK generate Schur functions in the ring of symmetric functions.^[25]

Matroids

A matroid is formally defined as a pair (E, \mathcal{I}), where E is a finite ground set and \mathcal{I} is a collection of subsets of E called the independent sets, satisfying three axioms: (I1) the empty set is independent; (I2) every subset of an independent set is independent; and (I3) if A, B \in \mathcal{I} with |A| < |B|, then there exists an element x \in B \setminus A such that A \cup \{x\} \in \mathcal{I}.^[33] These axioms capture the essence of independence in various combinatorial structures, generalizing concepts like linear independence in vector spaces.^[33] Algebraically, a matroid is representable over a field F if there exists a matrix over F whose columns are indexed by E such that the independent sets correspond precisely to the linearly independent columns.^[33] Not all matroids are representable over every field; for instance, binary matroids are those representable over the field with two elements, \mathrm{GF}(2).^[33] The rank function r: 2^E \to \mathbb{N} \cup \{0\} of a matroid is defined by r(S) = \max \{ |T| : T \subseteq S, T \in \mathcal{I} \} for any subset S \subseteq E, which measures the size of the largest independent subset of S.^[34] This function is submodular, satisfying r(A) + r(B) \geq r(A \cup B) + r(A \cap B) for all A, B \subseteq E, and monotonic non-decreasing.^[34] Key structures in matroids include the lattice of flats, where a flat is a subset F \subseteq E such that no element outside F can be added without increasing the rank, i.e., r(F \cup \{e\}) > r(F) for all e \notin F.^[35] The collection of all flats, ordered by inclusion, forms a geometric lattice, which is atomistic and semimodular.^[35] The Whitney numbers of the second kind for a matroid are the cardinalities w_k of the sets of flats of rank k, for k = 0, \dots, r(E), providing a combinatorial invariant analogous to binomial coefficients in the Boolean lattice.^[36] The Tutte polynomial T(M; x, y) of a matroid M is defined as T(M; x, y) = \sum_{A \subseteq E} (x-1)^{r(E) - r(A)} (y-1)^{|A| - r(A)}, encoding information about the ranks and sizes of subsets.^[37] Matroids find applications in several areas, including orientability, where an oriented matroid extends the structure by assigning signs to bases to model oriented dependencies, and every representable matroid over an ordered field admits such an orientation.^[38] Graphic matroids arise from undirected graphs, with the ground set as edges and independent sets as forests (acyclic subgraphs), capturing the cycle structure of the graph.^[39] Transversal matroids model bipartite matchings: given a bipartite graph with parts U and V, the ground set is U and independent sets are subsets of U that admit a matching into V.^[40] A fundamental result is the matroid intersection theorem, which states that for two matroids M_1 = (E, \mathcal{I}_1) and M_2 = (E, \mathcal{I}_2) on the same ground set, the size of the largest common independent set is \min_{S \subseteq E} \{ r_1(S) + r_2(E \setminus S) \}, where r_1 and r_2 are the respective rank functions.^[41] This min-max theorem enables polynomial-time algorithms for finding maximum common independents and has broad implications in optimization.^[41]

Advanced Applications

Association Schemes

An association scheme consists of a finite set X with v = |X| elements, together with a partition of the set of unordered pairs \{x, y\} \subset X (with x \neq y) into d associate classes R_1, \dots, R_d, such that the universal relation R_0 = \{(x,x) \mid x \in X\} is included, and for any i, j, k = 0, \dots, d, the intersection number p_{ij}^k—defined as the number of z \in X such that (x, z) \in R_k and (z, y) \in R_j for fixed x, y \in R_i—is constant and independent of the choice of x, y \in R_i. The relations R_i are symmetric, and the automorphism group of the scheme, which preserves the partition \{R_i\}, acts transitively on X. This structure generalizes partially balanced incomplete block designs and provides a framework for analyzing regular combinatorial relations through algebraic means. The adjacency matrices A_i (for i = 0, \dots, d), where (A_i)_{xy} = 1 if (x,y) \in R_i and 0 otherwise, satisfy A_0 = I_v (the identity matrix), \sum_{i=0}^d A_i = J_v (the all-ones matrix), A_i^T = A_i, and A_i A_j = \sum_{k=0}^d p_{ij}^k A_k. The Bose-Mesner algebra \mathcal{M} is the v \times v matrix algebra over \mathbb{C} generated by \{A_0, \dots, A_d\}, which is commutative, semisimple, and of dimension d+1. It admits a second basis consisting of primitive orthogonal idempotents E_0, \dots, E_d, where E_i E_j = \delta_{ij} E_i, \sum_{i=0}^d E_i = I_v, and each E_i is the projection onto a common eigenspace of the A_j. The eigenvalues are captured by the character tables: the matrix P with entries P_{ji} = p_j(i) (the eigenvalue of A_j on the space of E_i), and the dual Q with entries Q_{ji} = q_j(i) from the Krein parameters q_{ij}^k defined by E_i \circ E_j = \frac{1}{v} \sum_{k=0}^d q_{ij}^k E_k, where \circ denotes the Schur (entrywise) product; these satisfy PQ = vI_{d+1} and Q = v P^{-1}. Key properties of association schemes include feasibility conditions on the intersection array \{p_{ij}^k\}, such as the eigenvalues P_{ji} being algebraic integers and the Krein parameters q_{ij}^k being non-negative integers, ensuring the existence of the scheme. Delsarte's linear programming bound leverages the positive entries of P and Q to provide upper bounds on the size of codes or cliques in the scheme: for a subset C \subseteq X forming an R-clique (where distances are measured via the relations), |C| \leq v \frac{f(1)}{f(\alpha)} for certain polynomials f with non-negative coefficients in the basis of P, optimizing over such f. Association schemes find applications in coding theory through these bounds and in graph theory, where distance-regular graphs arise as metric association schemes (with relations corresponding to graph distances). Coherent configurations generalize association schemes by relaxing symmetry on the relations, allowing directed graphs while retaining the algebra structure. A fundamental theorem states that association schemes are closed under tensor products: if (X, \{R_i\}) and (Y, \{S_j\}) are schemes with d and e classes respectively, then the tensor product scheme on X \times Y has relations R_i \times S_j and R_i \times J_m (for |Y|=m), yielding de + d + e classes, with the Bose-Mesner algebra being the tensor product of the individual algebras. Strongly regular graphs provide examples of 2-class association schemes.

Strongly Regular Graphs and Finite Geometries

A strongly regular graph is defined as a connected, simple, undirected graph with v vertices that is k-regular, neither complete nor edgeless, such that any two adjacent vertices have exactly \lambda common neighbors and any two non-adjacent vertices have exactly \mu common neighbors, where $0 \leq \mu \leq \lambda < k and \mu \leq 1 if \lambda = 0. These graphs are characterized by the parameters (v, k, \lambda, \mu). A fundamental integrity condition relating the parameters is k(k - \lambda - 1) = (v - k - 1)\mu. The adjacency matrix A of a strongly regular graph has eigenvalue k with multiplicity 1, and two other eigenvalues \theta and \tau (with multiplicities f and g, respectively) given by the roots of the quadratic equation x^2 - (\lambda - \mu)x + (\mu - k) = 0, explicitly \theta, \tau = \frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2}, where \theta > 0 > \tau. Prominent examples include the Petersen graph, with parameters (10, 3, 0, 1), which has eigenvalues $3 (multiplicity 1), $1 (multiplicity 5), and -2 (multiplicity 4). Another is the Hoffman-Singleton graph, with parameters (50, 7, 0, 1), eigenvalues $7 (multiplicity 1), $2 (multiplicity 28), and -3 (multiplicity 21); it is the unique Moore graph of diameter 2 and degree 7. Conference graphs, arising from symmetric conference matrices of order $4t + 1, are strongly regular with parameters (4t + 1, 2t, t - 1, t), such as the Paley graph of order 5 (the cycle graph C_5) with parameters (5, 2, 0, 1). Finite geometries provide concrete realizations of strongly regular graphs through incidence structures. A projective plane of order q (where q is a prime power) consists of q^2 + q + 1 points and the same number of lines, with each line containing q + 1 points, each point incident with q + 1 lines, any two points determining a unique line, and any two lines intersecting in a unique point. Desarguesian projective planes are constructed as the projective geometry \mathrm{PG}(2, q) over the finite field \mathbb{F}_q, coordinatized by 3-dimensional vectors modulo scalars. Affine planes of order q have q^2 points and q(q + 1) lines, each line with q points and parallel classes partitioning the lines. Ovals in a projective plane of order q are sets of q + 1 points with no three collinear, maximizing the size of such sets; for example, in \mathrm{PG}(2, q), they correspond to conics over \mathbb{F}_q. Algebraic combinatorics links these geometries to strongly regular graphs via the eigenvalues of their adjacency matrices, often analyzed within the framework of association schemes where the collinearity relation forms a single non-trivial associate class. Blocking sets are minimal point sets intersecting every line, with the Bruen bound stating size at least q + 1 + \sqrt{q} for non-trivial ones in \mathrm{PG}(2, q). Baer subplanes are subplanes of order \sqrt{q} (when q = n^2) embedded in a plane of order q, covering n + 1 points per line of the ambient plane and inducing strongly regular point graphs. Key theorems constrain these structures. The Krein bounds for strongly regular graphs require the Krein parameters q_i \geq 0 for i = 0, 1, 2, yielding inequalities like $1 + \frac{v f \theta (\theta + \tau - \lambda + \mu)^2}{k (k - \tau)(\theta - \tau)^2} \leq \theta^2 and analogous for \tau, limiting feasible parameter sets. The Fano plane, the unique projective plane of order 2 with 7 points and 7 lines (each with 3 points), exemplifies uniqueness; its isomorphism class is the only one satisfying the axioms for q = 2, proven by exhaustive verification of incidence configurations.

References

[1]
[PDF] 18.212: Algebraic Combinatorics Introduction
Stanley-style (also enumerative, algebraic, or geometric) combinatorics deals with counting objects or their connections with algebra and geometry, and that's ...
[2]
MIT - 18.312 - Algebraic Combinatorics - Spring 2011 - Lionel Levine
In algebraic combinatorics, one associates algebraic objects like groups, rings and vector spaces to combinatorial objects in order to reveal more of their ...Missing: definition | Show results with:definition
[3]
Math 566: Combinatorial Theory
Course Description: Algebraic combinatorics is the study of combinatorial objects that arise in group theory and representation theory (like tableaux) and ...
[4]
[PDF] Algebraic Combinatorics
Jan 29, 2010 · ... algebraic means. V ... What is Algebraic Combinatorics? A general counting problem. Four properties. An algebraic approach. Summary. Wait!
[5]
Algebraic combinatorics - University of Waterloo
In algebraic combinatorics we might use algebraic methods to solve combinatorial problems, or use combinatorial methods and ideas to study algebraic objects.
[6]
[PDF] Enumerative and Algebraic Combinatorics
Enumeration, otherwise known as counting, is the oldest mathematical subject, while algebraic com- binatorics is one of the youngest. Some cynics claim.
[7]
Algebraic Combinatorics - Programs Detail - SLMath
Algebraic combinatorics is an area of mathematics that employs methods in abstract algebra in combinatorial contexts.
[8]
Algebraic Combinatorics
The combinatorics could be enumerative, coding theory, root systems, design theory, graph theory, incidence geometry or other topics. The key requirement is not ...
[9]
Algebraic combinatorics meets probability: statistical mechanics and ...
In this minicourse we will start with introducing basic tools and theorems from Algebraic Combinatorics which have seen wide applications in Statistical ...Missing: coding | Show results with:coding
[10]
[PDF] TOPICS IN ALGEBRAIC COMBINATORICS
This book is intended primarily as a one-semester undergraduate text for a course in algebraic combinatorics. The main prerequisites are a basic.
[11]
[PDF] The Evolution of Group Theory: A Brief Survey - Israel Kleiner
Mar 14, 2004 · In several major papers in 1815 and 1844 Cauchy inaugurated the theory of permutation groups as an autonomous subject. ... "Since the symmetric ...
[12]
MacMahon's conjecture on symmetric plane partitions - PubMed
In 1898, P. A. MacMahon conjectured that the generating function for symmetric plane partitions with at most s rows and each part at most j has an especially ...Missing: 1890s | Show results with:1890s
[13]
Georg Frobenius (1849 - 1917) - Biography - University of St Andrews
Hence 1897 is the year in which the representation theory of groups was born. Over the years 1897-1899 Frobenius published two papers on group representations, ...
[14]
Alfred Young - Biography - MacTutor - University of St Andrews
In 1900 he introduced 'Young tableau', the method for which he is best remembered. He wrote a series of papers On quantitative substitutional analysis which ...
[15]
[PDF] Enumerative and Algebraic Combinatorics in the 1960's and 1970's
Algebraic geometry had a long history of connections with combinatorics, such as the Schubert calculus and determinantal varieties. In the 1970's the theory ...
[16]
[PDF] Introduction to association schemes - Pure
Jan 1, 1991 · These notions go back to Bose and Mesner (1959). Example 1. A strongly regular graph is a 2-association scheme, where A1 and A2 denote the.
[17]
[PDF] Coding Theory: The story of how an engineering problem evolved ...
Jun 15, 2025 · Many techniques from graph theory, algebra, and finite geometry were used to construct these codes and began what is often referred to as ...
[18]
[math/0608288] The Combinatorics of Quiver Representations - arXiv
Aug 11, 2006 · This paper describes faces of codimension for quivers, relates to Klyachko cone facets, and applies to Littlewood-Richardson coefficients. It ...Missing: post- 2000
[19]
[PDF] Cluster algebras, quiver representations and triangulated categories
Abstract. This is an introduction to some aspects of Fomin-Zelevinsky's cluster algebras and their links with the representation theory of quivers and with ...
[20]
[PDF] Symmetric Functions and Hall Polynomials - UC Berkeley math
This book, 'Symmetric Functions and Hall Polynomials', by IG Macdonald, is a second edition, and includes topics such as Abelian groups and Hall polynomials.
[21]
[PDF] Enumerative Combinatorics Volume 1 second edition - Mathematics
Enumerative combinatorics has undergone enormous development since the publication of the first edition of this book in 1986. It has become more clear what are ...
[22]
Une théorie combinatoire des séries formelles - ScienceDirect.com
A categorical approach is used to formulate it. A new proof of Cayley's formula for the number of labelled trees is given as well as a new combinatorial proof ...
[23]
[PDF] Introduction to the Theory of Species of Structures
Nov 25, 2013 · [333] Y.N. Yeh, On the Combinatorial Species of Joyal, Ph.D. Dissertation, State University of. New York at Buffalo, 1985. Page 134. 130.Missing: original | Show results with:original
[24]
[PDF] Structure and enumeration of (3+1)-free posets - arXiv
In this paper, we give generating functions for (3+1)-free posets with unlabelled and labelled vertices in terms of the generating functions for bicoloured ...
[25]
Young Tableaux - Cambridge University Press & Assessment
The aim of this book is to develop the combinatorics of Young tableaux and to show them in action in the algebra of symmetric functions, representations of ...
[26]
[PDF] 4 Young Tableaux and the Representations of the Symmetric Group
Young tableaux are fillings of boxes with numbers, and they are used to describe irreducible representations of the symmetric group.
[27]
semistandard Young tableau in nLab
Nov 29, 2022 · In combinatorics a (semi-)standard Young tableau is a labelling of the boxes of a Young diagram with positive natural numbers (a Young tableau) ...Definition · Examples · Properties
[28]
hook length formula in nLab
Dec 26, 2024 · Given a partition (Young diagram) λ of n (boxes), the number (1) of standard Young tableaux of shape λ equals the factorial of n over the ...
[29]
RSK, the Robinson–Schensted–Knuth correspondence
Oct 10, 2025 · The Robinson–Schensted–Knuth correspondence (RSK), is a bijection between matrices with non-negative integer entries and pairs of semi-standard Young tableaux ...
[30]
Robinson-Schensted-Knuth correspondence in nLab
Aug 2, 2024 · Robinson-Schensted-Knuth correspondence is a combinatorial bijection sending matrices with non-negative integer entries to pairs of semistandard Young tableaux.
[31]
[PDF] Random matrix minor processes related to percolation theory
Performing the singular value decomposition, we ... of the corresponding pair of the Young tableaux, which is a random Young diagram, follows the ... associated to ...
[32]
A jeu de taquin theory for increasing tableaux, with applications to ...
We introduce a theory of jeu de taquin for increasing tableaux, extending fundamental work of Schützenberger (1977) for standard Young tableaux.
[33]
[PDF] Lecture 8: Matroids
Oct 8, 2009 · Definition 4 A binary matroid is a linear matroid that can be represented over GF(2). A matroid is regular if it is representable over any field ...
[34]
[PDF] Chapter 1 Definitions and basic examples
1.2 The rank function. We define the rank function of a matroid M as a function rM from 2E(M) to non- negative integers where rM(X) is defined to be the size ...
[35]
[PDF] LECTURE 3 Matroids and geometric lattices
We are now ready to characterize the lattice of flats of a matroid. Theorem 3.8. Let L be a finite lattice. The following two conditions are equivalent. (1) L ...
[36]
[PDF] What is a matroid? - LSU Math
Indeed,. Gian-Carlo Rota, whose many important contributions to matroid theory in- clude coauthorship of the first book on the subject [9], mounted a campaign.
[37]
[PDF] a convolution formula for the tutte polynomial
Let M be a finite matroid with rank function r. We will write A ⊆ M when we mean that A is a subset of the ground set of M, and write M|A and M/A for.
[38]
Orientability of matroids - ScienceDirect.com
Oriented matroids are defined, and every coordinatization of a matroid over an ordered field induces an orientation. Binary matroids are orientable if and only ...
[39]
MATROIDS AND GRAPHS
The circuits of a graph define a matroid. A matroid is graphic if it's the bond-matroid of a graph, and a graph is planar if its circuit-matroid is graphic.
[40]
[PDF] Transversals and matroid partition
In section 6, the matching matroids are shown to be simply the transversal matroids. 1'01' the most part, sectIons 2, 3, 4- 5, and 6 can be read separately.
[41]
[PDF] 5. Lecture notes on matroid intersection 5.1 Examples
Mar 30, 2011 · We now prove Theorem 5.1 by exhibiting an algorithm for finding a maximum cardinality independent set common to two matroids and a corresponding ...
[42]
[PDF] Association Schemes - University of Waterloo
Jun 3, 2010 · These notes provide an introduction to association schemes, along with some related algebra. Their form and content has benefited from ...
[43]
[PDF] An algebraic approach to the association schemes of coding theory
DELSARTE. ') Thesis, Universite Catholique de Louvain, June 1973. Promoter: Professor Dr J. M. Goethals. Philips Res. Repts Suppl. 1973, No. 10. Page 2 ...
[44]
https://ieeexplore.ieee.org/document/5392463
[45]
[PDF] An Introduction to Finite Projective Planes - David Kurniadi Angdinata
2.1 The projective plane of order 2 (Fano plane) . ... By construction, there are Hall planes of order n = p2q for q ∈ N and prime p ∈ N.Missing: parameters | Show results with:parameters
[46]
[PDF] Segre's theorem on ovals in Desarguesian projective planes
A projective plane is Desarguesian if it is constructed from a three dimensional vector space over a field (or more generally, a division algebra). Equiva-.
[47]
Baer subplanes - Project Euclid
The real plane is a Baer subplane of the complex projective plane in the following sense: each complex line contains a real point and, dually, each complex ...
[48]
BAER SUBPLANES IN FINITE PROJECTIVE AND AFFINE PLANES
The existence of Baer subplanes is well known in the case when T is a desarguesian projective or affine plane of square order n = m2. Then the following results ...