3-Uniform Friendship Hypergraphs

by Derrick Stolee

A very brief welcome to EXCILL2 participants. Thanks for visiting!

Today we discuss On a question of Sós about 3-uniform friendship hypergraphs by Hartke and Vandenbussche. These authors presented several new examples of friendship hypergraphs exhibiting a property that was not known to be possible. Their method applies careful use of integer programming as a black box. First, a careful construction of an integer linear program discovered some examples (and non-existence of examples) for small orders. Then, by making some symmetry assumptions, they constructed some larger integer programs that found larger examples, hinting towards an infinite family. The existence of larger examples remains open, although Lia, van Reesa, Seoa, and Singhi recently proved some structure theorems that apply to the examples found by Hartke and Vandenbussche.

Friendship Graphs and Hypergraphs

A friendship graph is a graph where every pair of vertices has a unique common neighbor (or “friend in common”). The Friendship Theorem of Erdős, Rényi, and Só completely characterized these graphs to be a very simple family: a set of (n-1)/2 triangles all sharing exactly one vertex. This one vertex in common then forms a universal friend. (These graphs are uniquely C_5-saturated.) This completes the discussion on friendship graphs, but there are several ways to generalize the concept to hypergraphs.

Figure 1. The first four friendship graphs.

Figure 1. The first four friendship graphs.

We use a generalization due to Sós.

Definition. A friendship 3-hypergraph is a 3-uniform hypergraph where for every set of three vertices x, y, z there exists a unique fourth vertex w (called the completion of xyz) such that the hypergraph contains the three edges xyw, xzw, and yzw.

Sós built friendship 3-hypergraphs that contain a universal friend (a vertex w such that for all pairs x,y the edge wxy is in the hypergraph) when n \equiv 2 \pmod 6 or n \equiv 4 \pmod 6. The question remained: do friendship 3-hypergraphs require this universal friend?

Overview of Method

I want to take a moment to summarize the thought process that likely went through the authors’ minds when they were performing this research. This process is mostly a projection of my own process into their work, but it is probably a good one. They started with the question, and followed these steps:

  1. Prove simple structural properties of the objects, if they exist.
  2. Formulate a computational method based on those properties.
  3. Execute the method and consider the results.
  4. Based on properties of small examples, guess properties of larger examples.
  5. Use those stronger properties to form a new computational method.
  6. Execute and report the results (with success!).

Ok, let’s get back to the research.

Properties of a Friendship 3-Hypergraph

The authors found the following properties that must be satisfied by any friendship 3-hypergraph:

  1. Every pair u, v of vertices appears in an at least one edge.
  2. Every edge is contained within a unique copy of K_4^3, the complete 3-hypergraph of order 4.
  3. There are at least \frac{1}{2}n(n-1) edges.
  4. There are at least \left\lceil\frac{n(n-2)}{8}\right\rceil copies of K_4^3.

In our ILP formulation, we focus on the copies of K_4^3. It may seem odd to use \binom{n}{4} variables when we could use \binom{n}{3} for the edges, but the structure of these complete subgraphs make the constraints much simpler and significantly restricts the structure of the subhypergraphs that are built as subsolutions to the full program. This is even more evident when we include indicator variables for the completion relationships.

The Integer Program Formulation

We now use these structural properties to build an integer linear program. Let our vertex set be V(H) = \{0,\dots,n-1\} and for all A \subset V(H) with |A| =4, let x_A be the binary indicator variable for whether the subgraph induced by A is a copy of K_4^3. We also include for every set S \subset V(H) with |S| = 3 and vertex v \in V(H) -S the variable y_S^v, which has value 1 if and only if v is the completion of S and S is a nonedge. Thus, every edge T has exactly one set A \supset T with x_A = 1 and every nonedge S has exactly one vertex v\notin S with y_S^v = 1. We encode this as the following constraint:

    (F) \sum_{A \supset S} x_{A} + \sum_{v \notin S} y_S^v = 1 for all S \in \binom{V(H)}{3}.

We now need to connect these variables in such a way that when y_S^v = 1 for S = \{x, y, z\}, the three edges vxy, vxz, and vyz are present in the hypergraph and thus are present in some copy of K_4^3. We add three new 0/1 variables B_S^{v,1}, B_S^{v,2}, B_S^{v,3} for each pair S, v. Always let S = \{x,y,z\}.

    (B1) B_{S}^{v,1} = \sum_{w \notin \{x,y,z,v\}} x_{\{w,v,x,y\}}.
    (B2) B_{S}^{v,2} = \sum_{w \notin \{x,y,z,v\}} x_{\{w,v,x,z\}}.
    (B3) B_{S}^{v,3} = \sum_{w \notin \{x,y,z,v\}} x_{\{w,v,y,z\}}.

It remains to encode that y_S^v = 1 if and only if each B_S^{v,1}, B_S^{v,2}, and B_S^{v,3} have value 1.

    (L) y_S^v \geq B_S^{v,1} + B_S^{v,2} + B_S^{v,3}.
    (U1) y_S^v \leq B_S^{v,1}.
    (U2) y_S^v \leq B_S^{v,2}.
    (U#) y_S^v \leq B_S^{v,3}.

Since this integer program is extremely symmetric, a solver would spend a lot of time revisiting isomorphic copies of subsolutions already visited, so the authors added a trivial constraint by setting y_{\{0,1,2\}}^3 = 0. This broke the symmetry enough that CPLEX was able to complete its search when n \leq 10.

Theorem (Hartke, Vandenbussche). There do not exist friendship 3-hypergraphs on 6, 7, or 9 vertices, and all friendship 3-hypergraphs on 10 vertices have a universal friend.

Also, when the integer program is run with n = 8, Sós’ construction could be returned as an answer, so the authors added one final constraint. Observe that a universal friend v would have y_S^v + x_{S\cup \{v\}} = 1 whenever v \notin S. If y_S^v = 1, then there are three K_4^3‘s that are forced by this, so we only look at the K_4^3-degree of a vertex to forbid a universal friend. A universal friend would have \binom{n-1}{2} incident edges, and hence would be contained in \frac{1}{3}\binom{n-1}{2} copies of K_4^3.

    (D) $\sum_{A \owns v} x_A \leq \frac{1}{3}\binom{n-1}{2} – 1$ for all v \in V(H).

With this constraint and applying some optimization tricks, the authors found the following theorem.

Theorem (Hartke, Vandenbussche). There exists a unique friendship 3-hypergraph {\mathcal F}_8 of order 8 with no universal friend.

The friendship 3-hypergraph {\mathcal F}_8 has an algebraic representation, but I prefer the following geometric one. Let V({\mathcal F}_8) be the vertices of the 3-dimensional cube. The copies of K_4^3 within {\mathcal F}_8 correspond to the planes that hit four vertices in the cube. See the figure below for an attempt at diagramming this interpretation.

Figure 2. Friendship Hypergraph.

Figure 2. The friendship 3-hypergraph {\mathcal F}_8. The planes correspond to copies of K_4^3. The six faces are lifted from the cube for effect.

Building Larger Instances from Smaller Instances

After finding an instance on 8 vertices, the authors though to wisely notice that 8 is a power of 2 and try doubling the number of vertices. While the program is intractable to solve from scratch, they made the following assumptions that a solution could satisfy:

  1. (Inductive Property) A solution on n = 2^k vertices contains two vertex-disjoint copies of a solution on 2^{k-1} vertices. Call these vertex sets the parts.
  2. (Pair Partition Property) The two parts partition into pairs such that each pair in one part forms a K_4^3 with every pair in the other part.
  3. (Automorphism Property) If we consider the vertices to be the elements of the group $G = latex ({\mathbb Z})^k$, then the group G acts on the hypergraph by addition. That is, if a \in G is an element and v \in G is a vertex, the automorphism \varphi_a associated with a has \varphi_a(v) = v + a.

The Automorphism Property could perhaps be seen as a “lucky guess” but is still a good idea, especially because {\mathcal F}_8 satisfies this property. This fits in with what I call “Symmetry as Constraint” in order to drastically reduce the branching factor of a search. If certain variables are set to be equal by some group action, then instead of having a search space of size 2^{M} (where M is the number of variables) we have a search space of size roughly 2^{M/C} (where C is the average size of a variable orbit). This constant reduction in the exponent corresponds to a polynomial reduction in the base (i.e. 2^{M/C} = (\sqrt[C]{2})^M). This is a huge reduction.

With these constraints, the authors found two new instances on 16 vertices and one on 32 vertices. Relaxing the pair partition property they found a third instance on 16 vertices. These constructions are detailed in the paper.

It remains open whether or not such constructions exist for other powers of two. The exponential growth in n makes this already difficult problem even more challenging to tackle. So, either you can wait until computers are fast enough to handle these cases or get to work finding more constraints and better algorithms. Perhaps some sort of structure could be inferred from these examples?

References

Stephen G. Hartke, Jenniver Vendenbussche, On a question of Sós about 3-uniform friendship hypergraphs, Journal of Combinatorial Designs, 16(3), pages 253–261 (2008).

P.C. Lia, G.H.J. van Reesa, Stela H. Seoa, N.M. Singhi, Friendship 3-hypergraphs, Discrete Mathematics, 312(11), pages 1892–1899 (2012).

V. T. Sós, Remarks on the connection of graph theory, finite geometry and block designs. Colloquio Internazionale sulle Teorie Combinatorie 2, pages 223-233 (1976).

Advertisements