18.212 Algebraic Combinatorics Notes

Search Ctrl K

18.212 Algebraic Combinatorics Notes

Search Ctrl K

Zettelkasten

Math

Algebra

inverse permutation

Category Theory

partially ordered set (poset)

Theoretical CS

increasing binary tree

Unfiled

absorption probability

adjacency matrix of product of graphs is tensor of adjacency matrices

Cauchy-Binet formula

complement of a graph

complete bipartite graph

cone over a graph

directed matrix tree theorem

effective resistance

electrical network

f_G of disjoint union

hypercube graph

incidence matrix

increasing tree

Kirchoff's laws

Kirchoff's matrix of an electrical network

Kirchoff's matrix tree theorem

Laplacian (Kirchoff) matrix

Linstrom-Gessel-Viennot theorem

number of labellings on a tree with given degrees

number of parking functions

oriented incidence matrix of a graph is totally unimodal

oriented incidence matrix

parking function

paths on differential posets and rooks

potential function

product of graphs

reciprocity formula for f_G

reduced Laplacian matrix

small degree polys don't intersect hyperplanes everywhere

spectrum of a graph

totally unimodal matrix

walks on differential posets

weighted matrix tree theorem

Y-delta transform

18.212 Algebraic Combinatorics

Abel's binomial formula

adjacency matrix

associated poset to a permutation

bijection between size k subsets and n-k subsets

Boolean lattice

Catalan numbers

Cayley's formula

conjugate partition

covering relation

cycles of a permutation

DeBruijn's theorem

descent of a permutation

differential poset

Dilworth's theorem

distinct parts and partitions with less than k parts

Dyck paths is Catalan

equidistributed

Euler's pentagonal number theorem

Eulerian numbers are coefficients of Eulerian polynomial

Eulerian numbers

Eulerian polynomial

Eulerian statistic

Eulerian triangle

exceedance is equidistributed to antiexceedance

exceedance is Eulerian

Fibonacci's lattice

first entry of schensted shape is length of longest increasing subsequence

generalized binomial theorem

generating function for size of young diagrams

generating function

Greene's theorem (posets)

Greene's theorem

Hardy-Ramanujan's theorem

hook length formula

inversion of a permutation

Jacobi's triple product formula

k-queue sortable

Knuth's hook length formula for trees

lambda(P(w)) is schensted shape

lattice of order ideals

Mahonian statistic

Mirsky's theorem

multiplicity of a partition

Narayana numbers

Narayana triangle

necessary conditions for scd

number of 3-permutation-avoiding permutations is catalan

number of complete binary trees with n+1 leaves is catalan

number of increasing binary trees with n vertices and k left edges is Eulerian numbers

number of non-cross perfect matchings with 2n vertices is catalan

number of non-crossing partitions with n vertices is catalan

number of permutations that are 2-queue sortable is catalan

number of permutations that are stack-sortable is catalan

number of plane binary trees with n vertices is Catalan

number of triangulations of a convex (n+2)-gon is catalan

number of valid parenthesization of n+1 letters is catalan

partition function

partitions with odd parts is equal to partitions with distinct parts

pattern avoidance

pentagonal numbers

plane binary tree

product of chains has a SCD

product of posets

q-binomial coefficient

q-binomial coefficients are generating functions for size of bounded young diagrams

q-factorial is generating functions of inversions of permutations

rank symmetric poset

rank unimodal poset

record (permutation)

records is Sterlingian

Robinson-Schensted-Knud (RSK) correspondence

saturated chain

Schensted insertion algorithm

Schensted shape

Sperner's theorem

statistic on permutations

Sterlingian statistic

sum over squares of number of SYTs is n!

symmetric chain decomposition

the number of SYTs of shape (n, n) is catalan

valid parenthesizations

weak exceedance

Young tableau(x)

Young's lattice

Select a result to preview

Enter to select

to navigate

ESC to close

spanning tree

Tags: #definition

spanning tree

Let $G$ be a graph. A spanning tree of $G = (V, E)$ is a subgraph $T = (V, E^{'})$ that is a tree.

Connected Pages

Depth

spanning tree

spanning tree

Pages mentioning this page

18.212 Algebraic Combinatorics

Kirchoff's matrix tree theorem

hypercube graph