TheoremDep
Track dependencies between theorems.
Learn more
Packing:
 Bin packing and Knapsack

1D:
 1BP: ⌈size(I)⌉ ≤ opt(I)
 1BP: NextFit(I) ≤ ⌈size(I)/(1ε)⌉ for εsmall items
 1BP: NextFit(S) ≤ ⌈2size(S)⌉
 Pseudopolynomial time algorithm for 1D knapsack
 FPTAS for 1D knapsack
 1BP: extending by small items
 1BP: linear grouping
 1BP: APTAS
 1BP is (1.5ε)inapprox
 1BP: FPTAS for config LP
 1BP: harmonic grouping
 1BP: KarmarkarKarp algorithm (broken)
 1BP: config LP's dual gives a DFF
 Geometric:

Config Lp:
 Bin packing: configuration LP
 1BP: size(I) ≤ lin(I)
 Bin packing: densityrestricted config LP
 Bin packing: config LP is not affected by grouping identical items
 Bin packing: removing density restriction from config LP
 Bin packing: config LP of predecessor
 Bin packing: dual of the densityrestricted config LP
 Bin packing: dual of config LP
 Bin packing: config LP dual solution increases with size
 BP: α(1+ε)approx solution to densityrestricted config LP using αapprox algorithm for densityrestricted knapsack
 BP: α(1+ε)approx solution to config LP using αapprox algorithm for knapsack
 Bin packing: union of input instances
 Bin packing: predecessor of an input instance
 Bin packing: configenum algorithm
 Measure Theory:

Graph Theory:
 Graph
 Cut in a graph
 Degree sum and number of edges
 Adjacency matrix
 Transpose of a graph
 Topological sort
 Path in Graph

Shortest Paths:
 Triangle inequality of shortest paths
 Edge relaxations
 Convergence of edge relaxations
 Subpath of shortest path is shortest path
 Shortestpath tree
 Edge relaxations: Predecessor subgraph is a rooted tree
 Edge relaxations: Predecessor subgraph is a shortestpath tree after convergence
 Dijkstra's algorithm
 Shortest path weight is ∞ iff there is a negativeweight cycle

Trees:
 Tree
 Tree iff acyclic and adding edge creates cycle
 Adding edge between 2 trees gives a tree
 Tree iff connected and deleting edge disconnects
 Rooted tree
 The undirected version of a rooted tree is a free tree
 Acyclic predecessor graph is union of rooted trees
 Deleting edge from tree gives 2 trees
 E = V  1 in trees
 Tree has at least 2 leaves
 G = (V, E) is a tree iff G is acyclic and E = V1
 G = (V, E) is a tree iff G is connected and E = V1
 Spanning Trees:
 Breadthfirst search
 DAG
 SCC graph is acyclic
 SCC graph
 Removing cycles can make a path shorter
 Forest

Dfs:
 Properties of DFS
 DFS: Edge classification
 DFS: Reverse sorting by finish time gives topological ordering
 DFS: Parenthesis theorem
 DFS: Whitepath theorem
 DFS on undirected graph gives spanning forest
 Directed graph is cyclic iff DFS gives back edges
 DFS: Edge classification in undirected graphs
 Undirected graph is cyclic iff DFS gives back edges
 DFS: Online edge classification
 DFS: low
 Kosaraju's Algorithm
 In a connected graph (V, E), E ≥ V  1
 Bridge in graph
 Deleting bridge from graph gives 2 components
 Geometry:

Matroids:
 Matroid
 Examples:
 Weights:
 Restriction of a matroid
 Matroid: circuit
 Matroid: rank
 Matroid: basis
 Matroid: basis iff size is rank
 Matroid: expanding to basis
 Matroid: basis of set increment
 Matroid: rank of set increment
 Matroid: dependent iff has circuit
 Matroid: nondisjoint circuits
 Matroid: unique circuit
 Matroid: rank is submodular
 Matroid: restricted rank is submodular

Set Functions:
 Set function
 Maximin share of a set function
 Subadditive and superadditive set functions
 Additive set function
 Supermodular function
 A supermodular function is also a superadditive function
 Submodular function
 A submodular function is also a subadditive function
 A set function is additive iff it is submodular and supermodular iff it is subadditive and superadditive.
 Sum of submodular functions is submodular

Fair Division:
 Fair division
 Notions:
 Impl:
 Non Impl:
 Non Existence:
 Combinatorics:

Abstract Algebra:

Groups:
 Group
 Homomorphism:

Isomorphism:
 Isomorphism on Groups
 Inverse of a group isomorphism is a group isomorphism
 Abelianness is invariant under isomorphism
 Isomorphism of groups is an equivalence relation
 Cayley's Theorem
 Cyclicness is invariant under isomorphism
 Order of elements is invariant under isomorphism
 Zm × Zn is isomorphic to Zmn iff m and n are coprime
 Inverse of product of two elements of a group
 Identity of a group is unique
 Order of element in finite group is finite
 Subgroup

Permutation Groups:
 Permutation group
 Product of cycles and a transposition
 Permutation is disjoint cycle product
 Permutation is transposition product
 Product of disjoint cycles is commutative
 Canonical cycle notation of a permutation
 Parity of a permutation
 Transposition bijects even and odd permutations
 Alternating Group
 Normal Subgroup
 Factor Groups:
 External direct product is a group
 Order of element in external direct product
 Inverse of a group element is unique
 Conditions for a subset to be a subgroup
 Cyclic Groups:
 Condition for a subset to be a subgroup
 First isomorphism theorem
 Third isomorphism theorem
 Second isomorphism theorem
 Order of element divides order of group
 Group element to the power group size equals identity
 Zn* is a group
 Cosets:

Rings:
 Ring
 Isomorphism:
 Integral Domain
 Characteristic of ring equals additive order of unity
 0x = 0 = x0
 (a)b = a(b) = ab
 Ideal
 Field
 A finite integral domain is a field
 A field is an integral domain
 Quotient Ring
 I is a maximal ideal iff R/I is a field
 I is a prime ideal iff R/I is an integral domain
 Conditions for a subset of a ring to be a subring
 Principal ideal
 Every ideal of Z is a principal ideal
 Zn is a ring
 Zp is an integral domain
 Zp is a field
 Semiring

Groups:

Polynomials:
 Polynomial
 GCD of polynomials
 Irreducible polynomial
 Degree of product of polynomials
 Zero divisors of a polynomial
 Degree of factor is less than degree of polynomial
 Polynomial divisibility
 q(x)F[x] is in p(x)F[x] iff p(x) divides q(x)
 Degree of sum of polynomials
 Polynomials of a ring form a ring
 Comparing coefficients of a polynomial with disjoint variables
 p(x)F[x] = F[x] iff p is a nonzero constant
 Polynomial division theorem
 Polynomial GCD theorem
 Factor theorem
 The ideal generated by an irreducible polynomial is maximal
 Product of linear factors is a factor
 A polynomial of degree n has at most n zeros
 F[x]/p(x): A ring
 The ring F[x]/p(x) is a field iff p is irreducible
 Every ideal in F[x] is principal
 F[x]/p(x) is isomorphic to F[x]/p(x)F[x]
 A polynomial in rationals is a rational times a polynomial in integers
 Gauss' Lemma
 Eisenstein's criterion

Linear Algebra:
 Vector
 Dotproduct of vectors
 pnorm

Vector Spaces:
 Vector Space
 Linear independence
 Affine independence (incomplete)
 Zeros in vector space
 Negation in vector space
 Span
 Decrementing a span
 Incrementing a linearly independent set
 Condition for being a subspace

Basis:
 Basis of a vector space
 A set of dim(V) linearly independent vectors is a basis
 Spanning set of size dim(V) is a basis
 Minimally spanning iff basis
 Preserving a basis by replacing a vector
 Basis of F^n
 Coordinatization over a basis
 Basis changer
 Maximally linearly independent iff basis
 Linearly independent set can be expanded into a basis
 Linearly independent set is not bigger than a span
 Dimension of a set of vectors
 span(A)=span(B) & A=B & A is linindep ⟹ B is linindep

Linear Transformation:
 Linear transformation
 Composition of linear transformations
 Vector space isomorphism is an equivalence relation
 Symmetric operator
 Range of linear transformation is subspace of codomain
 Kernel of linear transformation is subspace of domain
 Matrix of linear transformation
 Basis change is an isomorphic linear transformation
 Vector spaces are isomorphic iff their dimensions are same
 Canonical decomposition of a linear transformation
 Symmetric operator iff hermitian
 Basis of range of linear transformation
 Matrix of orthonormal basis change

Inner Product Spaces:
 Inner product space
 Inner product is antilinear in second argument
 Orthogonality and orthonormality
 GramSchmidt Process
 A set of mutually orthogonal vectors is linearly independent
 Joining orthogonal linindep sets
 Zero in inner product
 CauchySchwarz Inequality
 Pythagorean theorem
 Coordinatization over orthogonal vectors
 x and y are parallel iff ∥x∥²∥y∥² = < x, y >².
 Triangle inequality
 Orthonormal basis change matrix

Matrices:
 Matrix
 Stacking:
 Matrix multiplication is associative
 Positive definite
 Sum of positive definite matrices is positive definite
 Reduced Row Echelon Form (RREF)
 Rows of RREF are linearly independent
 Matrix multiplication distributes over addition
 c(AB) = (cA)B and (AB)c = A(Bc)
 Conjugate Transpose and Hermitian
 Transpose of product
 Conjugation of matrices is homomorphic
 Submatrix
 Determinants:
 Trace of a matrix
 Matrices over a field form a vector space
 Row space
 Matrices form an innerproduct space
 Elementary row operation
 Every elementary row operation has a unique inverse
 Row equivalence of matrices
 Row equivalent matrices have the same row space
 RREF is unique
 Identity matrix
 Identity matrix is identity of matrix product
 Inverse of a matrix
 Inverse of product
 Elementary row operation is matrix premultiplication
 Row equivalence matrix
 Rank of a matrix
 A matrix is fullrank iff its rows are linearly independent
 Fullrank square matrix in RREF is the identity matrix
 Fullrank square matrix is invertible
 AB = I implies BA = I
 Orthogonal matrix
 Bounding matrix quadratic form using eigenvalues
 Positive definite iff eigenvalues are positive
 RREF([AI]) = [Iinv(A)] iff A is invertible
 Square matrices form a (semi)ring
 System Of Linear Equations:

Eigenvectors:
 Eigenvalues and Eigenvectors
 All eigenvalues of a hermitian matrix are real
 All eigenvalues of a symmetric operator are real
 Real matrix with real eigenvalues has real eigenvectors
 Eigenspace
 Eigenvectors of distinct eigenvalues are linearly independent
 Diagonalization
 Characteristic polynomial of a matrix
 Degree and monicness of a characteristic polynomial
 Every complex matrix has an eigenvalue
 Symmetric operator on V has a basis of orthonormal eigenvectors
 Orthogonally diagonalizable iff hermitian
 A is diagonalizable iff there are n linearly independent eigenvectors
 Eigenpair of affine transformation
 Bound on eigenvalues of sum of matrices
 Eigenpair of power of a matrix

Number Theory:
 Gcd:
 Prime Factorization:
 Modular Equivalence
 Modular multiplication
 Modular addition
 Coprime
 Euler's Totient Function
 Integer Division Theorem
 GCD partitioning of Zn
 If x divides ab and x is coprime to a, then x divides b
 Euclid's lemma
 ab is coprime to x iff a and b are coprime to x
 Multiplication permutes Zn*
 LCM divides common multiple
 ϕ is multiplicative
 Product of coprime divisors is divisor
 GCD times LCM equals product
 Sum of ϕ of divisors
 Existence of Modular Inverse
 Euler's Theorem
 Chinese remainder theorem

Complexity:
 Np Completeness:
 Optimization:

Convexity:
 Cone
 Convex combination and convex hull
 Vertex of a set
 Transitivity of convexity
 Convex set

Polyhedra:
 Polyhedral set and polyhedral cone
 FourierMotzkin Elimination
 Basic feasible solutions
 BFS is vertex
 Condition for existence of BFS in a polyhedron
 Point in polytope is convex combination of BFS
 Implicit equality
 Interior point of polyhedron
 Dimension of a polyhedron
 Double directions of a polyhedron (incomplete)
 Pointing a polyhedron
 Finitely generated set is polyhedron
 Extreme point iff BFS
 BFS iff vertex iff extreme point
 Condition for polyhedral cone to be pointed
 Recession cone of a polyhedron
 Polyhedron is unbounded iff it has direction
 Bounded section of pointed cone
 Representing point in pointed polyhedral cone
 Representing point in fullrank polyhedron
 LP is optimized at BFS
 Double direction of a convex set and double recession space
 Convex hull of a finite number of points in Euclidean space is bounded
 Extreme point of a convex set
 Vertex implies extreme point
 Condition for a point to be extreme
 Direction of a convex set and Recession cone
 Extreme directions of a convex set
 Extreme direction of convex cone as extreme point of intersection with hyperplane

Probability:
 Prob And Events:

Rand Vars:
 Random variable
 Median:
 Expected value of a random variable
 Probability: limit of CDF
 Conditioning over random variable
 Distribution of sum of random variables (incomplete)
 Conditional expectation
 Law of total probability: E(Y) = E(E(YX)) (incomplete)
 Law of total probability: P(A) = E(P(AX)) (incomplete)
 Law of total probability: decomposing expectation over countable events
 Independence of random variables (incomplete)
 Expectation of product of independent random variables (incomplete)
 X ≤ Y ⟹ E(X) ≤ E(Y)
 Counting process
 X and Y are independent implies X and f(Y) are independent
 Linearity of expectation
 Variance:
 Linearity of expectation for matrices
 CauchySchwarz inequality for random variables

Markov Chains:
 Markov chain
 Markov chains: long run proportion of a state
 Markov chains: recurrent states
 Markov chains: recurrent iff infinite visits
 ChapmanKolmogorov equation
 Markov chains: accessibility and state classes
 Markov chains: long run proportion is inverse of time to reenter (incomplete)
 Markov chains: recurrent state to acessible state (incomplete)
 Markov chains: positive recurrence
 Markov chains: positive recurrence is a class property
 Markov chains: finite sink is positive recurrent
 Markov chains: recurrent iff expected number of visits is infinite
 Markov chains: recurrence is a class property
 Markov chains: recurrent class is sink
 Markov chains: finite sink is recurrent (incomplete)
 Distrs:
 Conc Ineq:
 Normal Distr:
 Poisson Process:
 Analysis:
 Bounds:
 Misc: