|
|
|
The Kruskal-Katona Theorem
|
The word simplex has two different
meanings in math, depending on whether we are talking about geometry or topology; like many other terms shared between these
two fields, there are similarities between the concepts, but some important physical properties in the geometric definition
are no longer present in the topological definition.
In geometry, it is easiest to look at the 2-dimensional
simplex (a solid triangle in a plane) and the 3-dimensional simplex (a solid tetrahedron in 3-space) and then extrapolate
the method of creating an n-dimensional simplex from a (n-1)-dimensional
simplex. If we define a 0-dimensional simplex as a single point, we then create a 1-dimensional simplex by choosing
a point in 1-dimension away from our 0-dimensional simplex, then connecting the new point to the old 0-dimensional simplex.
We get a line segment. Then, we put the line segment in 2-dimenisonal space, find a non-colinear point and connect that
point to every point in our line segment to create the 2-dimensional simplex, a solid triangle. The pattern remains
the same as we move from 2 dimensions to 3, from 3 dimensions to 4, etc.
In topology, an n-dimensional simplex is the power set of a set with n+1 elements.
For example, let's look at how the power set of {1,2,3} can be shown to be similar to the solid triangle.
|
Subsets of {1,2,3}
|
Geometric equivalent
|
{1,2,3}
|
Interior of the triangle
|
{1,2}, {1,3}, {2,3}
|
Edges of the triangle
|
{1}, {2}, {3}
|
Vertices of the triangle
|
Ø (the empty set)
|
No physical representation
|
In the triangle, the three
edges would be defined as the boundary of the simplex. For a tetrahedron, the
boundary would be the four triangle faces. In general, the n-dimensional simplex
has n+1 boundary elements, sometimes referred to as facets.
A simplicial complex is a collection of simplices; if all the simplices are of the
same dimension, it is called regular or uniform.
If a regular simplicial complex A has m simplices
and all the simplices are of dimension k-1, how many facets will the complex have?
The maximum is easy to calculate; if we assume that no two simplices share a facet, there will be mk facets. To find out the minumum number of facets, we need to find the k-binomial
representation of m. Identity #1200015 states that there is a unique representation
of any positive integer m as follows.
Since m is the cardinality of A,
the Kruskal-Katona Theorem says we can represent the lower bound for the cardinality of the boundary of A in terms of the k-binomial representation of m as follows.
|
|
