2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is up to isomorphism a unique such structure on N=4 elements. I recommend asking the question for N not a multiple of 3. Gerhard "You May Get More Answers" Paseman, 2018.06.28. $\endgroup$ – Gerhard Paseman Jun 28 '18 at 20:15
  • $\begingroup$ I am now thinking that the answer is that up to isomorphism, there is exactly one such structure for N=4k, and no structures otherwise. You should be able to prove this for yourself by combinatorial reasoning. Gerhard "Not Many Ways To Group" Paseman, 2018.06.28. $\endgroup$ – Gerhard Paseman Jun 28 '18 at 20:27
  • $\begingroup$ In the proposed counter example it looks like there are two sets whose intersection has one element, namely [9,8,6] and [1,4,8]. $\endgroup$ – John Machacek Aug 28 '18 at 19:16
  • $\begingroup$ @JohnMachacek Oops, my bad. $\endgroup$ – Mohammad Al-Turkistany Aug 28 '18 at 19:21
  • $\begingroup$ @JohnMachacek Should I post a new question about the case where two triples intersect at most in two elements? $\endgroup$ – Mohammad Al-Turkistany Aug 28 '18 at 19:23
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I thought I had a counter-example to your claim "the union cannot contain five elements", but realized I was mistaken, so have deleted that response! I'll post the correct part of my response here: We can think of each triple as defining a triangle (2-simplex).The condition |T∩S|∈{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. $\endgroup$ – James Jun 29 '18 at 1:46
  • $\begingroup$ These two geometric conditions do in fact imply that every vertex belongs to one of a collection of disjoint tetrahedrons (as you pointed out). Your formula $(4k)!/(k!(4!)^k)$ could be obtained by taking k disjoint tetrahedrons, looking at all labelings of those tetrahedrons, and quotienting out by symmetries among and within each tetrahedron. All this is just to give a geometric interpretation of this question. $\endgroup$ – James Jun 29 '18 at 1:50
  • $\begingroup$ I normally do not encourage edits to my posts. In this case though, you might add (bracketed by "Edit by James" or something like that) your interpretation below the main part of the post (and above the signature, please). I think it is good to have a geometric interpretation to aid the combinatorial version, which can be hard to visualize. Joseph O'Rourke does it as a separate answer, so you could do it that way if you prefer. Gerhard "Sometimes Pictures Make A Proof" Paseman, 2018.06.28. $\endgroup$ – Gerhard Paseman Jun 29 '18 at 1:56
  • $\begingroup$ I created a new post, with a picture, to not crowd out your reasoning. $\endgroup$ – James Jun 29 '18 at 3:15
  • $\begingroup$ Nice, Do you know whether Exact cover by 3-sets problem is NP-complete for this family of triples? $\endgroup$ – Mohammad Al-Turkistany Jun 29 '18 at 20:08
3
$\begingroup$

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):

diagram

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.