Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
7  
Dave, if you have an answer to your own question you should feel free to post it as an answer and accept it. –  Qiaochu Yuan Oct 8 '10 at 10:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.