most recent 30 from http://mathoverflow.net 2013-05-19T06:38:34Z http://mathoverflow.net/feeds/question/41123 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41123/cliques-of-hyperedges Dave Pritchard 2010-10-05T10:27:22Z 2010-10-08T10:40:34Z

<p>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:</p> <ul> <li>A star: there is a vertex such that every edge of $C$ contains it</li> <li>A triangle: there are three vertices such that every edge of $C$ goes between two of them</li> </ul> <p>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.)</p> <p>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?</p> <p>Note that $f(r) \ge \Omega(r^2)$ by considering projective planes.</p> <p>Cross-post asking for a good algorithm to find a max-clique: <a href="http://cstheory.stackexchange.com/questions/1846/max-clique-in-line-graph-of-hypergraph" rel="nofollow">http://cstheory.stackexchange.com/questions/1846/max-clique-in-line-graph-of-hypergraph</a></p> <p>Answer: I have found there was a series of results on this function $f$, and that this set $S$ is often called a <i>kernel</i>. 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})$.</p>