A Small Debt Regarding Turan’s Problem

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:

\dim H_1(K,F) \le n-2.

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 {n-1} \choose {2}. 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. H_1(K) is still spanned by the cycles c(e) for all edges e={i,j} 1<i<j \le n. Let H be a maximal set of edges e so that all the corresponding c(e) are linearly independent in H_1(K). 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 H_1(K). 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 \dim H_1(K) \le n-2.

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

 

About these ads
This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

2 Responses to A Small Debt Regarding Turan’s Problem

  1. Tim Ramsey says:

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s