**Turan’s problem **asks for the minimum number of triangles on n vertices so that every 4 vertices span a triangle. (Or equivalently, for the maximum number of triangles on n vertices without a “tetrahedron”, namely without having four triangles on four vertices.) When we discussed Turan’s problem, we stated a lemma without giving the proof. Here is the proof.

**Lemma: **A three uniform hypergraph G on n vertices, so that every four vertices span a triangle satisfies:

.

Here, K is the simplicial complex on the n vertices which has all possible edges and, in addition, the triangles in G. F can be any field of coefficients, below we assume that F=Z/2. (But very little changes are required for the general case.)

**Proof:** A little **background**: The space of 1-dimensional cycles of the complete graph with n vertices is of dimension . Start with the star T where vertex ’1′ is adjacent to all other vertices. every edge e={i,j} not in T, determines a cycle c(e) supported by the triangle {1,i} {1,j} and {i,j}. It is easy to see that all these cycles are linearly independent in the space of cycles of the complete graph and span this space.

Now to the **proof itself**. Let G be a hypergraph with the property that every 4 vertices span a triangle and let K be the 2-dimensional simplicial complex obtained by adding the triangles in G to the complete graph. is still spanned by the cycles c(e) for all edges e={i,j} . Let H be a maximal set of edges e so that all the corresponding c(e) are linearly independent in . It suffices to prove:

**Claim:** H is a forest.

To see this assume that H contains a cycle, and choose such a cycle C with a minimum number of vertices.

We will consider linear relations between the c(e)’s where e is an edge with vertices from {2,3,…,n}, in . Note that

(a) If a triangle {1,i,j} belongs to G then c(i,j)=0. (We write c(i,j) instead of c({i,j}).)

(b) if {i,j,k} belongs to G, 1<i<j<k, then c(i,j)+c(i,k)+c(j,k)=0.

Note also that every 4 vertices 1,i,j,k span a triangle and therefore

(c) either c(i,j)=0, c(i,k)=0, c(j,k)=0 or, c(i,j)+c(i,k)+c(j,k)=0.

Case 1: C is a triangle: this is impossible by (c).

Case 2: C is a cycle with at least four vertices. Consider three consecutive vertices i,j,k on C. from the four possibilities in (c), the first and third will give us an edge e in the cycle with c(e)=0, and the last possibility will allow us to “shortcut” and replace C by deleting ij and jk and adding ik. Therefore, we are left with the third possibility

(d) c(i,k)=0.

Now, consider 4 consecutive vertices on C, i,j,k,m. We know that c(i.k)=c(j,m)=0. Suppose w.l.g. that the triangle {i,j,k} is in H. It follows that c(i,j)=c(j,k), a contradiction.

Since H is a forest on the n-1 vertices {2,3,…,n}, H contains at most n-2 edges, and therefore .

Extensions to other Turan type problems, and a more conceptual proof for this lemma, may be of interest.

I recently came accross your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed reading. Nice blog.

Tim Ramsey

Good day!,