Find the edges in a Hypergraph

Question

I have 8 vertices. I need to form hyperedges such that each edge should contain exactly 4 vertices and each edge should intersect with every other edge at exactly 2 vertices. How many edges are there(maximum)? I believe the answer to be 7, but how?. I got the answer by listing down the possible combinations. Is there an algorithmic approach? I need to find a generalized approach for this. Any help would be much appreciated. Thank You

Maximum number of edges on a graph

Answer 1

I suppose when you say that the "answer is 7", you refer to the minimal number of hyperedges on your hypergraph for a valid solution.

Let's clarify things algebraically. You have a set $V = \{ v_i | i \in [[1, n]]\}$ of $n$ vertices, and a set $E$ of hyperedges over V (ie, $E \subset P(V)$). You are looking for the minimal number of hyperedges $m_e$ such that the condition "all hyperedges contains $m_v$ vertices, and the intersection of any two hyperedges contains $m_i$ vertices".

In this case, the solution is actually trivial: no hyperedges at all. But since this is a bit of a dumb problem (since the solution is always trivial), I suppose you might have the additional condition "all vertices must be covered by at least one hyperedge".

In this case we have $n = 8$, $m_v = 4$ and $m_i = 2$. We'll use an algorithmic approach. Since there is no distinctive factor between each vertex at this point, they are symmetrical, in the sense that any can be picked as our starting point. Our goal is thus to cover each vertex, while keeping the conditions $\forall e \in E, card(e) = m_v$ and $\forall e_1, e_2 \in E, card(e_1 \cap e_2) = m_i$.

So we start by covering a set of $m_v$ vertices with a first edge $e_1 = \{v_1, v_2, v_3, v_4\}$. Both conditions are still true (since there is no second edge to intersect with, the second is 'trivially true'). Note that here, symmetry is broken: some edges are covered by one hyperedge, others are covered by none. However, by symmetry among the hyperedges that are covered by none, we can pick any $m_v - m_i = 2$ extra vertices, and make an edge with those, and $m_i$ of vertices from the existing hyperedge. This will make it so our new hyperedge indeed has $m_v$ vertices. In our case, we pick the hyperedge $e_2 = \{v_1, v_2, v_5, v_6\}$. Both conditions are still true.

At this point we can notice that symmetry is broken again. Vertices $v_1$ and $v_2$ are covered by the 2 hyperedges; vertices $v_3$ and $v_4$ are covered by 1 hyperedge; vertices $v_5$ and $v_6$ are covered by another 1 hyperedge; and vertices $v_7$ and $v_8$ are not covered.

Our algorithm requires us to minimize the total number of hyperedges, while making a full cover, and respecting some conditions. So we'll start by trying to cover the uncovered vertices. This implies that our new hyperedge HAS to cover $m_v - m_i = 2$ "new" (uncovered) vertices, and intersect over $m_i = 2$ vertices, in a way that doesn't break the intersection condition for any of our previous hyperedges.

Such a hyperedge must then contain $v_7$ and $v_8$, and two other vertices. Among the vertices that are already covered, we have to take $m_i$ vertices such that the intersection condition is respected. The only set of $m_i$ extra vertices that respects this condition is the set $\{v_1, v_2\}$, thus resulting in the hyperedge $e_3 = \{v_1, v_2, v_7, v_8\}$. Additionally, our problem is solved at this point.

Precisely: $E = \{\{v_1, v_2, v_3, v_4\}, \{v_1, v_2, v_5, v_6\}, \{v_1, v_2, v_7, v_8\}\}$. As you can see, in this setup, all vertices are covered, and the 2-by-2 intersections of hyperedges only ever have 2 elements (the set $\{v_1, v_2\}$). Finally, $m_e = 3$, not $7$.

NB:

• This is a naive algorithm I came up with on the spot. It'd take time and skills (which I'm not sure I really have) to prove it.
• Consequently, I'm not sure how well it generalizes. For example, this algorithm would not find non-minimal solutions such as $E = \{\{v_1, v_2, v_3, v_4\}, \{v_3, v_4, v_5, v_6\}, \{v_5, v_6, v_7, v_8\}, \{v_7, v_8, v_1, v_2\}\}$.
• My gut feeling is that symmetry arguments are important for this problem, and that group theory can play a role. I wouldn't know how to justify this gut feeling though.
• Finding the set of all sets of hyperedges which are a solution to this restricted covering problem will require group theory, if only to handle counting all distinct valid re-labellings of vertices.
• There is probably a way to define group theoretic equivalence classes of solutions and thus some form of hypergraph quotients based on this problem.

If anyone has some references on this problem, or hypergraphs in general: I'm interested as well.

Answer 2

The maximum is indeed $7$.

Upper bound

With each edge $e$ we associate $8$ triples ($3$-element sets) of vertices, namely, the $4$ triples contained in $e$ and the $4$ triples disjoint from $e$. No triple is associated with two different edges; this follows from the fact that the edges intersect in exactly two vertices. If we have $n$ edges then we have $8n$ distinct triples of vertices. Since there are just $8$ vertices, it follows that $\8n\le\binom83$, i.e., $n\le\binom83/8=7$.

Lower bound

In fact, on a set of just $7$ points, we can family a family of $7$ $4$-sets such that any two of them intersect in exactly two points. Note that the complements of the $4$-sets are $3$-sets, and two $4$-sets intersect in exactly two points if and only if their complements intersect in exactly one point. Thus an equivalent problem is to find a system of $7$ triples on $7$ points such that any two triples intersect in exactly one point. This is a well known construction; look up Steiner triple system or Fano plane.