The paper is mainly interested in cliques of graphs. A clique is a set of vertices such that every pair of them forms an edge. A set with 0 or 1 vertices is automatically a clique. A set of 2 vertices is a clique precisely if they are connected by an edge. The set of three vertices on the far left above form a clique, for example. The set of three furthest to the top right do not form a clique, however, as the top vertex and the far right one are not connected by an edge.

If we have a graph, we can count its cliques of various sizes. Every graph has 1 clique on zero vertices, as there is exactly one way to pick none of the vertices. There are 5 cliques on one vertex (the five vertices) and 6 cliques on two vertices (the six edges). There are also two cliques on three vertices (the vertex sets of the two triangles). We can list these numbers to get the face vector of the graph. In this example, we get (1, 5, 6, 2).

The main problem to address is what integer vectors can possibly be face vectors of graphs. For example, if we have 5 vertices, the above graph shows that we could have six edges. By making all possible pairs of vertices connected by an edge, we could have 10 edges. But a graph with five vertices cannot possibly have more than ten edges.

The problem becomes harder if we are dealing with larger cliques. For example, if a graph has 60 cliques on three vertices, then what is the most cliques on four vertices it could possibly have? Unlike where we start with vertices, there isn't an obvious way to maximize this.

A result of Frankl, Furedi, and Kalai characterized the face vectors of balanced complexes in the mid 1980s. Several years later, Kalai and Eckhoff independently conjectured that graphs had to satisfy the same characterization. We prove their conjecture.