Counting triples family with double shared elements

Question

We have a set of elements $S=\{1,2,3, . . . , N\}$ and family $F$ of $N$ triples of elements in $S$ ($N$ is a multiple of 3). Each element of $S$ appears in exactly three triples. The elements in each triple are distinct. The intersection of two triples $T_1, T_2$ is either empty or has exactly two elements ( $|T_1 \cap T_2|=2$). I guess this should be a well known combinatorial object.

What is the number of such family of triples for each N?

I encountered this object in constructing special instances of exact cover problem. Some of the families have exact cover.

Answer 1

I'm guessing that what matters here is subsets of size 3 from S, and that F is a special collection of such sets. It turns out that F meeting the conditions is very special, and to see this, we relax the condition on N and assume it an arbitrary large enough positive integer, instead of having three divide N.

So pick an element from S, and look at the three sets containing that element. Since they all contain this element, are distinct sets, and every two intersect in exactly two elements as they are supposed to, the union of these three sets is either four or five elements of S.

Suppose it is five elements. Then each of the three sets contain the same two elements, as two of the sets have four elements among them, the third set has the fifth element, and so the third subset shares two elements with each of the other two subsets, and must share them with the intersection. We thus have two elements in three distinct triples, and three elements in one triple each. But any other allowed triple containing one of these three outer elements has to intersect the first triples in one element exactly (otherwise we get an element in four triples). So we cannot extend the set system this way without breaking one of the conditions. Thus the union cannot contain five elements.

Thus the union of the three triples is four elements. Then the three triples cover one element three times, and the three other elements twice. Any other triple that contains two of these three elements must contain the third, otherwise again we get a triple intersecting one of the triples in one element, or else we get an element in more than three triples. The only way out is to have a fourth triple cover all these three elements.

So there is such a set system for N=4. However, for larger N, we see the above analysis carves out four elements that are involved in four triples, and no other elements are involved in those triples. To have the set system cover the other elements, we repeat the argument to carve out four more elements. In general, we repeat this construction until we exhaust N, in which case N is a multiple of 4, and if the elements are unlabelled, then there is essentially only one such F. For labelled configurations, elementary combinatorics should yield something like $(4k)!/(k!(4!)^k)$ number of systems.

Gerhard "Four Isn't A Lonely Number" Paseman, 2018.06.28.

Answer 2

This post is just re-expressing Gerhard Paseman's answer in a more geometric way:

Think of each triple as defining a triangle (2-simplex).

• The condition $|T \cap S| \in \{0,2\}$ means any two simplices are either disjoint or share exactly one edge.

• The condition that every element is in exactly three triples says that every vertex has exactly three simplices attached to it.

These triangles together form a vertex-labeled simplcial complex. Gerhard Paseman's main claim amounts to: this simplicial complex must be a disjoint union of tetrahedra.

Let's try to prove this. Notice that since any two triangles share either an edge, or are disjoint, so any such simplicial complex can be constructed by gluing triangles together along edges, and then labeling the vertices at the end.

Let's consider a single connected component of this simplicial complex. It is easy to see that a connected component cannot have only one, two, or three triangles, as all such arrangements have vertices shared by only two triangles. Here are all possible connected arrangements of three triangles formed by gluing edges (ensuring no more than one edge is shared between triangles):

Any connected component with four or more triangles must be obtainable by starting with one of these possible arrangments and attaching more triangles along existing edges.

The left-most arrangement is already a dead end: the top and bottom triangles share only a point.

One can check that the middle arrangment is impossible to consistently extend by attaching even a single new triangle (one vertex will end up in four different triangles).

Finally, the only consistent way to extend the right-most arrangement is to glue a fourth triangle to the outermost edges, forming a tetrahedron. This tetrahedron cannot be extended.

This proves all such simplicial complexes are a disjoint union of tetrahedra. It suffices to count the number of ways of labeling the vertices of $k$ tetrahedra, up to symmetry. This is exactly $(4k)!/(k!(4!)^k)$. The $k!$ is from the symmetry of reordering the tetrahedra, and the $(4!)^k$ is from the symmetry of each tetrahedron.