Generalized octahedra and cliques in intersection graphs of uniform hypergraphs (Q1304822)

Let \(H\) be a \(k\)-uniform hypergraph with \(n\) vertices and \(m\) hyperedges. A \(t\)-intersection clique of \(H\) is a maximal set of hyperedges of \(H\), any two of which have at least \(t\) vertices in common. (Thus it is a maximal clique in the \(t\)-intersection graph of \(H\).) It follows from a result of Füredi that the number of such cliques is bounded by a polynomial in \(m\), if \(k\) and \(t\) are fixed. When \(t=k-1\), these cliques are easy to describe, and, in particular, it follows that there are at most \(m\) of them. The author concentrates on the case \(t=k-2\). By analyzing the structure of the possible \(k-2\)-intersection cliques in \(H\), he is able to deduce that there are at most \(O(mn)\) such cliques. Both these specialized bounds are much lower than those following from the general bounds in Füredi's theorem. As an application, one can compute in polynomial time the clique number of several classes of intersection graphs.