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)⌉
- Pseudo-polynomial 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: Karmarkar-Karp algorithm (broken)
- 1BP: config LP's dual gives a DFF
- Geometric:
-
Config Lp:
- Bin packing: configuration LP
- 1BP: size(I) ≤ lin(I)
- Bin packing: density-restricted 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 density-restricted config LP
- Bin packing: dual of config LP
- Bin packing: config LP dual solution increases with size
- BP: α(1+ε)-approx solution to density-restricted config LP using α-approx algorithm for density-restricted 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: config-enum 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
- Shortest-path tree
- Edge relaxations: Predecessor subgraph is a rooted tree
- Edge relaxations: Predecessor subgraph is a shortest-path tree after convergence
- Dijkstra's algorithm
- Shortest path weight is -∞ iff there is a negative-weight 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| = |V|-1
- G = (V, E) is a tree iff G is connected and |E| = |V|-1
- Spanning Trees:
- Breadth-first 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: White-path 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: non-disjoint 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 non-zero 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
- Dot-product of vectors
- p-norm
-
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 anti-linear in second argument
- Orthogonality and orthonormality
- Gram-Schmidt Process
- A set of mutually orthogonal vectors is linearly independent
- Joining orthogonal linindep sets
- Zero in inner product
- Cauchy-Schwarz 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 inner-product 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 pre-multiplication
- Row equivalence matrix
- Rank of a matrix
- A matrix is full-rank iff its rows are linearly independent
- Full-rank square matrix in RREF is the identity matrix
- Full-rank square matrix is invertible
- AB = I implies BA = I
- Orthogonal matrix
- Bounding matrix quadratic form using eigenvalues
- Positive definite iff eigenvalues are positive
- RREF([A|I]) = [I|inv(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
- Fourier-Motzkin 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 full-rank 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(Y|X)) (incomplete)
- Law of total probability: P(A) = E(P(A|X)) (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
- Cauchy-Schwarz 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
- Chapman-Kolmogorov 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: