### 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 triangles all sharing exactly one vertex. This one vertex in common then forms a *universal friend*. (These graphs are uniquely -saturated.) This completes the discussion on friendship graphs, but there are several ways to generalize the concept to hypergraphs.

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 there exists a unique fourth vertex (called the *completion* of ) such that the hypergraph contains the three edges , , and .

Sós built friendship 3-hypergraphs that contain a universal friend (a vertex such that for all pairs the edge is in the hypergraph) when or . 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:

- Prove simple structural properties of the objects, if they exist.
- Formulate a computational method based on those properties.
- Execute the method and consider the results.
- Based on properties of small examples, guess properties of larger examples.
- Use those stronger properties to form a new computational method.
- 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:

- Every pair of vertices appears in an at least one edge.
- Every edge is contained within a unique copy of , the complete 3-hypergraph of order 4.
- There are at least edges.
- There are at least copies of .

In our ILP formulation, we focus on the copies of . It may seem odd to use variables when we could use 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 and for all with , let be the binary indicator variable for whether the subgraph induced by is a copy of . We also include for every set with and vertex the variable , which has value 1 if and only if is the completion of *and* is a nonedge. Thus, every edge has exactly one set with and every nonedge has exactly one vertex with . We encode this as the following constraint:

(F) for all .

We now need to connect these variables in such a way that when for , the three edges , , and are present in the hypergraph and thus are present in some copy of . We add three new 0/1 variables for each pair . Always let .

(B1) .

(B2) .

(B3) .

It remains to encode that if and only if each , , and have value 1.

(L) .

(U1) .

(U2) .

(U#) .

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 . This broke the symmetry enough that CPLEX was able to complete its search when .

**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 , Sós’ construction could be returned as an answer, so the authors added one final constraint. Observe that a universal friend would have whenever . If , then there are three ‘s that are forced by this, so we only look at the *-degree* of a vertex to forbid a universal friend. A universal friend would have incident edges, and hence would be contained in copies of .

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

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

**Theorem (Hartke, Vandenbussche).** There exists a unique friendship 3-hypergraph of order 8 with no universal friend.

The friendship 3-hypergraph has an algebraic representation, but I prefer the following geometric one. Let be the vertices of the 3-dimensional cube. The copies of within correspond to the planes that hit four vertices in the cube. See the figure below for an attempt at diagramming this interpretation.

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

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

The Automorphism Property could perhaps be seen as a “lucky guess” but is still a good idea, especially because 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 (where is the number of variables) we have a search space of size roughly (where is the average size of a variable orbit). This constant reduction in the exponent corresponds to a polynomial reduction in the base (i.e. ). 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 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).

Hi Derrick

I was happy to find your review of the above papers and would like to answer some of your questions regarding the existence of other friendship hypergraphs.

We (Leif Kjær Jørgensen and I, Aalborg University, Denmark) recently studied the structure of the given hypergraphs from Hartke and Vandenbussche. We were able to find structural similarity in F8 and one of the F16 and from this knowledge construct an infinite family of friendship hypergraphs on 2^k vertices. We did however not use a computer for the construction.

Furthermore, we used a computer-search to find friendship hypergraphs on 20 and 28 vertices, by assuming them to be vertex-transitive.

We also found a 4-uniform friendship hypergraph on 9 vertices without a universal friend using the Steiner system S(5,6,12).

We have submitted our paper on the above.

If you have any questions, please feel free to contact me.

Best regards,

Anita Abildgaard Sillasen,

PhD-student, Aalborg University, Denmark

Very impressive, Anita! Do you have a draft available online? I’ll put it in my next Roundup.

Sorry for the late reply.

We just put a draft online here: http://www.math.aau.dk/index.php?id=244