Polyhedral combinatoricsPolyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral combinatorics falls into two distinct areas. Mathematicians in this area study the combinatorics of polytopes; for instance, they seek inequalities that describe the relations between the numbers of vertices, edges, and faces of higher dimensions in arbitrary polytopes or in certain important subclasses of polytopes, and study other combinatorial properties of polytopes such as their connectivity and diameter (number of steps needed to reach any vertex from any other vertex).
Abstract polytopeIn mathematics, an abstract polytope is an algebraic partially ordered set which captures the dyadic property of a traditional polytope without specifying purely geometric properties such as points and lines. A geometric polytope is said to be a realization of an abstract polytope in some real N-dimensional space, typically Euclidean. This abstract definition allows more general combinatorial structures than traditional definitions of a polytope, thus allowing new objects that have no counterpart in traditional theory.
Chordal graphIn the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.
6-polytopeIn six-dimensional geometry, a six-dimensional polytope or 6-polytope is a polytope, bounded by 5-polytope facets. A 6-polytope is a closed six-dimensional figure with vertices, edges, faces, cells (3-faces), 4-faces, and 5-faces. A vertex is a point where six or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron. A 4-face is a polychoron, and a 5-face is a 5-polytope.
Line perfect graphIn graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K_4, or a triangular book K_1,1,n. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.
Line graphIn the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.
Integral polytopeIn geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively. An -dimensional regular simplex can be represented as an integer polytope in , the convex hull of the integer points for which one coordinate is one and the rest are zero.
Complex polytopeIn geometry, a complex polytope is a generalization of a polytope in real space to an analogous structure in a complex Hilbert space, where each real dimension is accompanied by an imaginary one. A complex polytope may be understood as a collection of complex points, lines, planes, and so on, where every point is the junction of multiple lines, every line of multiple planes, and so on. Precise definitions exist only for the regular complex polytopes, which are configurations.
Bipartite graphIn the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.
Uniform 4-polytopeIn geometry, a uniform 4-polytope (or uniform polychoron) is a 4-dimensional polytope which is vertex-transitive and whose cells are uniform polyhedra, and faces are regular polygons. There are 47 non-prismatic convex uniform 4-polytopes. There are two infinite sets of convex prismatic forms, along with 17 cases arising as prisms of the convex uniform polyhedra. There are also an unknown number of non-convex star forms.
