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})$.

  • 7
    $\begingroup$ Dave, if you have an answer to your own question you should feel free to post it as an answer and accept it. $\endgroup$ Oct 8, 2010 at 10:51


Your Answer

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

Browse other questions tagged or ask your own question.