Suppose we have a graph, with multiple edges allowed. An edge-clique is a set $C$ of edges so that every two edges in $C$ share at least one endpoint. Note that any edge-clique falls into one of two categories:
- A star: there is a vertex such that every edge of $C$ contains it
- A triangle: there are three vertices such that every edge of $C$ goes between two of them
What kind of patterns persist for hypergraphs of rank $\le r$? (It has a vertex set, and "hyper"edges which are arbitrary sets of size at most $r$. Again an edge-clique is a family of pairwise intersecting edges.)
I believe one can show the following structure theorem: for every clique $C$, there is a set $S$ of at most $f(r)$ vertices, such that every pair of edges $C$ meet at at least one vertex in $S$. But the bound I have on $f(r)$ is something like doubly exponential. What is the best possible?
Note that $f(r) \ge \Omega(r^2)$ by considering projective planes.
Cross-post asking for a good algorithm to find a max-clique: https://cstheory.stackexchange.com/questions/1846/max-clique-in-line-graph-of-hypergraph
Answer: I have found there was a series of results on this function $f$, and that this set $S$ is often called a kernel. The best current bounds on $f$ are due to Tuza (Tuza, Z. (1985) Critical hypergraphs and intersecting set-pair systems. J. Combin. Theory Ser. B 39 134–145.); in short $f(r) = \Theta(4^r/\sqrt{r})$.
