Computational complexity theoryIn theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.
Cubic graphIn the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipartite graph. In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.
Flag (geometry)In (polyhedral) geometry, a flag is a sequence of faces of a polytope, each contained in the next, with exactly one face from each dimension. More formally, a flag ψ of an n-polytope is a set {F_–1, F_0, ..., F_n} such that F_i ≤ F_i+1 (–1 ≤ i ≤ n – 1) and there is precisely one F_i in ψ for each i, (–1 ≤ i ≤ n). Since, however, the minimal face F_–1 and the maximal face F_n must be in every flag, they are often omitted from the list of faces, as a shorthand. These latter two are called improper faces.
600-cellIn geometry, the 600-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {3,3,5}. It is also known as the C600, hexacosichoron and hexacosihedroid. It is also called a tetraplex (abbreviated from "tetrahedral complex") and a polytetrahedron, being bounded by tetrahedral cells. The 600-cell's boundary is composed of 600 tetrahedral cells with 20 meeting at each vertex. Together they form 1200 triangular faces, 720 edges, and 120 vertices.
Graph factorizationIn graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.
Linear complementarity problemIn mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968. Given a real matrix M and vector q, the linear complementarity problem LCP(q, M) seeks vectors z and w which satisfy the following constraints: (that is, each component of these two vectors is non-negative) or equivalently This is the complementarity condition, since it implies that, for all , at most one of and can be positive.
Hyperoctahedral groupIn mathematics, a hyperoctahedral group is an important type of group that can be realized as the group of symmetries of a hypercube or of a cross-polytope. It was named by Alfred Young in 1930. Groups of this type are identified by a parameter n, the dimension of the hypercube. As a Coxeter group it is of type B_n = C_n, and as a Weyl group it is associated to the symplectic groups and with the orthogonal groups in odd dimensions. As a wreath product it is where S_n is the symmetric group of degree n.
Pascal's triangleIn mathematics, Pascal's triangle is a triangular array of the binomial coefficients arising in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy. The rows of Pascal's triangle are conventionally enumerated starting with row at the top (the 0th row). The entries in each row are numbered from the left beginning with and are usually staggered relative to the numbers in the adjacent rows.
